代码随想录1刷—二叉树篇（一）

基础理论

区分满二叉树和完全二叉树

之前提到过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

二叉搜索树是有数值的了，二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树

平衡二叉树 / AVL树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是$logn$，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

**那么链式存储方式就用指针， 顺序存储的方式就是用数组。**顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在散落在各个地址的节点串联一起。

• 用数组来存储二叉树如何遍历的呢？

  如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历方式

• 深度优先遍历
  • 前序遍历（递归法，迭代法）：中左右
  • 中序遍历（递归法，迭代法）：左中右
  • 后序遍历（递归法，迭代法）：左右中
• 广度优先遍历
  • 层次遍历（迭代法）

深度优先和广度优先遍历实现方式

做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。之前讲栈与队列的时候说过，栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树的定义（链式）

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1
2
3
4
5
6

二叉树的遍历（递归版）

144. 二叉树的前序遍历（递归版）

class Solution {
public:
    void preorder(TreeNode* root, vector<int>& num){
        if(root == nullptr) return;
        num.push_back(root->val);
        preorder(root->left, num);
        preorder(root->right, num);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

94. 二叉树的中序遍历（递归版）

class Solution {
public:
    void preorder(TreeNode* root, vector<int>& num){
        if(root == nullptr) return;
        preorder(root->left, num);
        num.push_back(root->val);
        preorder(root->right, num);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

145. 二叉树的后序遍历（递归版）

class Solution {
public:
    void preorder(TreeNode* root, vector<int>& num){
        if(root == nullptr) return;
        preorder(root->left, num);
        preorder(root->right, num);
        num.push_back(root->val);
    }
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        preorder(root, ans);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉树的遍历（迭代版）

144. 二叉树的前序遍历（迭代版）

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root == nullptr) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

94. 二叉树的中序遍历（迭代版）

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur!=nullptr || !st.empty()){
            if(cur != nullptr){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

145. 二叉树的后序遍历（迭代版）

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root == nullptr) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if(node->left) st.push(node->left);
            if(node->right) st.push(node->right);
        }
        reverse(result.begin(), result.end()); 
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二叉树的统一迭代法

//中序
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*>st;
        if(root!=nullptr) st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node!=nullptr){
                st.pop();
                if(node->right) st.push(node->right);	//右
                st.push(node);							//中
                st.push(nullptr);
                if(node->left) st.push(node->left);		//左
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//前序遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*>st;
        if(root!=nullptr) st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node!=nullptr){
                st.pop();
                if(node->right) st.push(node->right);	//右
                if(node->left) st.push(node->left);		//左
                st.push(node);							//中
                st.push(nullptr);		
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//后续遍历
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*>st;
        if(root!=nullptr) st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node!=nullptr){
                st.pop();
                st.push(node);							//中
                st.push(nullptr);
                if(node->right) st.push(node->right);	//右
                if(node->left) st.push(node->left);		//左
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二叉树的层序遍历

二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现。

102. 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root != nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0;i < size; i++){   
                //千万不要直接写i<que.size(),因为for循环内que.pop();所以其size不断变化。
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

107. 二叉树的层序遍历 II

自底向上的层序遍历，其实正常从上到下遍历然后最后翻转就好啦_{只需要多加一行代码噢}

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

199. 二叉树的右视图（写错了很多次！注意！）

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0;i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                if(i == (size - 1)) result.push_back(node->val);    
                		//如果是每层最后一个，放入结果数组中。
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
        } 
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

637. 二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> result;
        if(root != nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            double sum = 0;
            for(int i = 0; i < size;i++){
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if(node->right) que.push(node->right);
                if(node->left)  que.push(node->left);
            }
            result.push_back(sum / size);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

429. N 叉树的层序遍历

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> result;
        if(root != nullptr)    
            que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> num;
            for(int i = 0;i < size;i++){
                Node* node = que.front();
                que.pop();
                num.push_back(node->val);
                for(int j = 0;j < node->children.size();j++){
                    if(node->children[j]) que.push(node->children[j]);
                }
            }
            result.push_back(num);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

559. N 叉树的最大深度

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        int depth = 0;
        if(root != nullptr)    
            que.push(root);
        while(!que.empty()){
            int size = que.size();
            depth++;
            for(int i = 0;i < size;i++){
                Node* node = que.front();
                que.pop();
                for(int j = 0;j < node->children.size();j++){
                    if(node->children[j]) que.push(node->children[j]);
                }
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class solution {
public:
    int maxdepth(node* root) {
        if (root == 0) return 0;
        int depth = 0;
        for (int i = 0; i < root->children.size(); i++) {
            depth = max (depth, maxdepth(root->children[i]));
        }
        return depth + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

515. 在每个树行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if(root != nullptr)
            que.push(root);
        while(!que.empty()){
            int size = que.size();
            int MaxValue = INT_MIN; 
            		//不要写0 如果二叉树上的值是-1那些负数就完啦！
            for(int i = 0;i < size;i++){
                TreeNode* node = que.front();
                que.pop();
                MaxValue = node->val > MaxValue ? node->val : MaxValue; 
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(MaxValue);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

116. 填充每个节点的下一个右侧节点指针（写错好几次！注意！）

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            Node* nodeOne;
            Node* node;
            for(int i = 0;i < size; i++){   
                if(i == 0){
                    nodeOne = que.front();
                    que.pop();
                    node = nodeOne;
                }else{
                    node = que.front();
                    que.pop();
                    nodeOne->next = node;
                    nodeOne = nodeOne->next;
                }
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            node->next = nullptr;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

117. 填充每个节点的下一个右侧节点指针 II

116是完全二叉树，本题为二叉树，实际上代码没有任何区别，逻辑一毛一样

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            Node* nodeOne;
            Node* node;
            for(int i = 0;i < size; i++){   
                if(i == 0){
                    nodeOne = que.front();
                    que.pop();
                    node = nodeOne;
                }else{
                    node = que.front();
                    que.pop();
                    nodeOne->next = node;
                    nodeOne = nodeOne->next;
                }
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            node->next = nullptr;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

104. 二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth = 0;
        queue<TreeNode*> que;
        if(root != nullptr){
            que.push(root);   
        }else{
            return 0;
        }
        while(!que.empty()){
            int size = que.size();
            depth++;
            for(int i = 0;i < size;i++){
                TreeNode *node = que.front();
                que.pop();
                if(node->right) que.push(node->right);
                if(node->left)  que.push(node->left);
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//超强递归…
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
1
2
3
4
5
6
7
8

111. 二叉树的最小深度

注意：最小深度是左右孩子都NULL

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; 
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right){
                // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//超强递归！
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right != NULL) {
            return 1 + minDepth(root->right);
        }
        if (root->left != NULL && root->right == NULL) {
            return 1 + minDepth(root->left);
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

226. 翻转二叉树

递归法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)
            return root;
        swap(root->right,root->left);	//交换左右节点
        invertTree(root->right);		//翻转左右子树
        invertTree(root->left);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11

（注意！此题不能用中序遍历！如果用中序遍历的话，有些节点可能翻转两次，可以画图看看。）

如果真的很想用中序遍历，那就两次都翻转一侧子树，就可以啦。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

迭代法

前序遍历迭代法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

层序遍历迭代法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != nullptr) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

中序遍历迭代法

迭代版本的中序遍历没有任何问题，用模板就可以，因为其是利用栈的，而不是靠指针来遍历，避免了递归法中翻转了两次的情况。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
      if (root == NULL) return root;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

N叉树的遍历

589. N 叉树的前序遍历（注意写法！！）

递归版

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> result;
    void traversal(Node* root){
        if(root == nullptr)
            return;
        result.push_back(root->val);
        for(int i = 0;i < root->children.size();i++){
            traversal(root->children[i]);
        }
    }
    vector<int> preorder(Node* root) {
        result.clear();
        traversal(root);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

迭代版

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> result;
        if (root == NULL) return result;
        stack<Node*> st;
        st.push(root);
        while (!st.empty()) {
            Node* node = st.top();
            st.pop();
            result.push_back(node->val);
            // 注意要倒叙，这样才能达到前序（中左右）的效果
            for (int i = node->children.size() - 1; i >= 0; i--) {
                if (node->children[i] != NULL) {
                    st.push(node->children[i]);
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

590. N 叉树的后序遍历

递归版

class Solution {
public:
    vector<int> result;
    void traversal (Node* root) {
        if (root == NULL) return;
        for (int i = 0; i < root->children.size(); i++) { // 子孩子
            traversal(root->children[i]);
        }
        result.push_back(root->val); // 中
    }

    vector<int> postorder(Node* root) {
        result.clear();
        traversal(root);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

迭代版

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> result;
        if (root == NULL) return result;
        stack<Node*> st;
        st.push(root);
        while (!st.empty()) {
            Node* node = st.top();
            st.pop();
            result.push_back(node->val);
            for (int i = 0; i < node->children.size(); i++) { // 相对于前序遍历，这里反过来
                if (node->children[i] != NULL) {
                    st.push(node->children[i]);
                }
            }
        }
        reverse(result.begin(), result.end()); // 反转数组
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

101. 对称二叉树

其实我们要比较的是根节点的左右子树，比较的是两个子树的里侧和外侧的元素是否相等。

递归版

class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right){
        if( (left!=nullptr&&right==nullptr) || (left==nullptr&&right!=nullptr))
            return false;
        else if(left==nullptr&&right==nullptr)
            return true;
        else if(left->val!=right->val)
            return false;
        else // left->val==right->val
            return compare(left->left,right->right) && compare(left->right,right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        return compare(root->left,root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

迭代版

因为都是成对比较，所以用队列还是栈都行无所谓。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

另一个思路是层序遍历，每层用相向指针遍历看val是否相等。（BFS广度优先搜索）

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        if(root == nullptr) return true;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> result(size);
            for(int i = 0;i < size; i++){   
                TreeNode* node = que.front();
                que.pop();
                result[i] = node ?  node->val : INT_MIN;
                //如果是空节点那我们给他赋个固定值就好啦~这里用INT_MIN
                if(node != nullptr){
                    que.push(node->left);	//只要根节点存在，无论其左右孩子是否为空都加！
                    que.push(node->right);
                }
            }
            for(int i = 0; i < size/2 ; i++){
                if(result[i] != result[size-1-i])  return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26