代码随想录算法训练营刷题复习9 ：二叉树复习之二叉树的遍历+求二叉树的属性（未完）

作者：喵喵爱编程 | 2024-06-29 15:04:49

踩

二叉树复习

二叉树的定义

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

二叉树的遍历+求二叉树的属性（未完）

递归遍历
①traversal函数，res数组存遍历结果
②终止条件：判空
③前序中左右；后序左右中；中序左中右；

前序遍历的迭代做法：
①stack,数组res
②while判断条件：st非空
node存栈顶元素，然后弹出栈顶，
中、左（先入后出，故先右入栈）、右（后左入栈）。

中序遍历的迭代做法：
左中右：
while判断条件cur非空||栈非空，
cur不空：入栈（继续将左子树的左结点入栈）；
否则：出栈、存值、找右孩子
后序遍历的迭代做法：
中左右->中右左->左右中

102. 二叉树的层序遍历
①借助queue,用二维数组res存储遍历结果（本题）
②root先入队列，while条件判断 que非空
存队列的元素个数size（for循环遍历的次数），定义vec数组用来暂存每一层的元素值（for循环结束放入res中）
for循环逐个处理size个元素（将其左右孩子节点入队）：
node存top，pop，vec保存值，左右孩入队
226. 翻转二叉树
①终止条件，判空
②借助swap翻转根节点的左右孩，
③然后递归传入左子树和右子树
101. 对称二叉树
此对称为镜像对称
①定义compare函数，参数传入需要判断的两个节点
②判断：
不符合的条件：左×(空),右√(不空)；左√，右×；左右√ 但是值不相同
符合的条件：左×右×，以及除去不符合条件的其他情况
再继续递归调用函数，保证左子树的左孩子、右子树的右孩子 + 左子树的右孩子、右子树的左孩子同时相等才成立

最大深度、最小深度、完全二叉树的个数，这三个题有异曲同工之处。
递归+有返回值+left、right+在return时添加对节点的处理

104. 二叉树的最大深度
使用递归实现，需要返回值
①终止条件：判空，返回0；
② left左子树的最大高度
③ right右子树的最大高度
④ return 1+max(left,right);
111. 二叉树的最小深度
和上一题同理，
终止条件：判空，返回0；
主要①左子树为空右子树不空②左子树不空右子树空 ③左右子树都不空
三种情况分开判断
222. 完全二叉树的节点个数
递归、有返回值
left左子树的个数
right右子树的个数
返回1+left+right

144. 二叉树的前序遍历

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

先序遍历的迭代做法：
①stack,数组res
②while判断条件：st非空
node存栈顶元素，然后弹出栈顶，
中、左（先入后出，故先右入栈）、右（后左入栈）。

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

94. 二叉树的中序遍历

class Solution {
public:
/*
递归遍历
①traversal函数，res数组存遍历结果 
②终止条件：判空
③前序 左中右；后序左右中；中序中左右；*/
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur==NULL) return;
        traversal(cur->left,vec);    //左
        vec.push_back(cur->val);    //中
        traversal(cur->right,vec);    //右
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

中序遍历的迭代做法：
左中右：
while判断条件cur非空||栈非空，
cur不空：入栈（继续将左子树的左结点入栈）；
否则：出栈、存值、找右孩子

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

145. 二叉树的后序遍历

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

后序遍历的迭代做法：
中左右->中右左->左右中

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

102. 二叉树的层序遍历
①借助queue,用二维数组res存储遍历结果（本题）
②root先入队列，while条件判断 que非空
存队列的元素个数size（for循环遍历的次数），定义vec数组用来暂存每一层的元素值（for循环结束放入res中）
for循环逐个处理size个元素（将其左右孩子节点入队）：
node存top，pop，vec保存值，左右孩入队

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        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!=NULL)
                    que.push(node->left);
                if(node->right!=NULL)
                    que.push(node->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};
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

226. 翻转二叉树
①终止条件，判空
②借助swap翻转根节点的左右孩，
③然后递归传入左子树和右子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
            return root;
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->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

101. 对称二叉树
此对称为镜像对称
①定义compare函数，参数传入需要判断的两个节点
②判断：
不符合的条件：左×(空),右√(不空)；左√，右×；左右√ 但是值不相同
符合的条件：左×右×，以及除去不符合条件的其他情况
再继续递归调用函数，保证左子树的左孩子、右子树的右孩子 + 左子树的右孩子、右子树的左孩子同时相等才成立

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right) {
        if(left==NULL && right==NULL)
            return true;
        else if(left==NULL && right!=NULL)
            return false;
        else if(left!=NULL && right== NULL)
            return false;
        else if(left->val != right->val)
            return false;
        
        bool judge_left = compare(left->left,right->right);
        bool judge_right = compare(left->right,right->left);
        return judge_left&&judge_right;
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL)
            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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

最大深度、最小深度、完全二叉树的个数，这三个题有异曲同工之处。
递归+有返回值+left、right+在return时添加对节点的处理

104. 二叉树的最大深度
使用递归实现，需要返回值
①终止条件：判空，返回0；
② left左子树的最大高度
③ right右子树的最大高度
④ return 1+max(left,right);

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        int height_l = maxDepth(root->left);
        int height_r = maxDepth(root->right);
        return 1+max(height_l,height_r);
    }
};
1
2
3
4
5
6
7
8
9
10

111. 二叉树的最小深度
和上一题同理，
终止条件：判空，返回0；
主要①左子树为空右子树不空②左子树不空右子树空 ③左右子树都不空
三种情况分开判断

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);
        }
        else {
            return 1+min(minDepth(root->left),minDepth(root->right));
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

222. 完全二叉树的节点个数
递归、有返回值

left左子树的个数
right右子树的个数
返回1+left+right

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL)
            return 0;
        int left = countNodes(root->left);
        int right = countNodes(root->right);
        return 1+left+right;
    }
};
1
2
3
4
5
6
7
8
9
10

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/769546