226.翻转二叉树 （优先掌握递归）

题目链接
思路：交换每个节点的左右子树即可，尝试使用递归法

递归法

提示：递归三部曲

1.确定递归函数的参数和返回值

TreeNode* invertTree(TreeNode* root)

2.确定终止条件

if(root == NULL) return root;

3.确定单层递归的逻辑

1
2
3
swap(root->left,root->right);
intvertTree(root->left);
invertTree(root->right);

代码如下：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    TreeNode* invertTree(TreeNode* root){
        if(root == NULL) return root;
        swap(root->left,root->right);
		intvertTree(root->left);
		invertTree(root->right);
        return root;
    }

迭代法

深度优先遍历

根据昨天的二叉树的前中后序遍历，进行改进。（先序遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(root!=NULL){
            TreeNode* cur = st.top(); //zhong
            st.pop();
            swap(cur->left,cur->right);
            if(cur->right) st.push(cur->right);//you
            if(cur->left) st.push(cur->left);//zuo
        }
        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
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* cur = st.top();              
            if(cur!=NULL){
                st.pop();
                if(cur->right) st.push(cur->right); // 右 
                if(cur->left) st.push(cur->left); // 左
                st.push(root); // 中
                st.push(NULL);
            }else{
                st.pop();
                cur=st.push();
                st.pop();
                swap(cur->left,cur->right);
            }
        }
        return root;
    }
};

广度优先遍历

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

            }
        }
        return root;
    }
};

101. 对称二叉树 （优先掌握递归）

思路：判断方法分情况：

  1. 左空右空、左右都非空且值相同 对称
  2. 其他情况（左右有一个为空、左右都非空且值不同） 不对称

按照以上分类情况，

104.二叉树的最大深度 （优先掌握递归）

什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。

大家 要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。

111.二叉树的最小深度 （优先掌握递归）

先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。