《劍指offer》-判斷對稱二叉樹 - zjutzz－IT工程師數位筆記本

文章出處

題目描述
請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。

思路上還是廣度優先搜索（BFS）來做的。BFS是依托于STL的queue作為容器作為存儲空間的，并且樹的每一層節點的處理都放到一個內部的while循環中；
使用一個vector存儲層內節點元素值，然后判斷這個vector是否為對稱的。如果對稱，還要考慮元素個數，除了第一層之外都應該是偶數個元素。這樣的話沒有考慮到null節點的處理。

如果節點為null則存儲一個0（假定樣例節點值都是大于0的），這樣就不用考慮vector元素個數的問題了。

代碼如下：

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if (pRoot == NULL){
            return true;
        }

        queue<TreeNode*> Q;
        Q.push(pRoot);

        bool first_layer = true;

        while (!Q.empty()){
            int lo = 0, hi = Q.size();
            vector<int> v;
            while (lo++ < hi){
                TreeNode* t = Q.front();
                Q.pop();
                if (t == NULL){
                    v.push_back(0);
                    continue;
                }
                else{
                    v.push_back(t->val);
                }
                if (t->left){
                    Q.push(t->left);
                }
                else{
                    Q.push(0);
                }
                if (t->right){
                    Q.push(t->right);
                }
                else{
                    Q.push(0);
                }
            }
            for (int i = 0; i < v.size() / 2; i++){
                if (v[i] != v[v.size() - 1 - i]){
                    return false;
                }
            }
        }
        return true;
    }
};