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

二叉树复习

二叉树的定义

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x),left(NULL),right(NULL) {}
};

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

1. 144. 二叉树的前序遍历(递归+迭代)
2. 94. 二叉树的中序遍历(递归+迭代)
3. 145. 二叉树的后序遍历(递归+迭代)

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

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

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

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

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

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

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

9. 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;
    }
};

先序遍历的迭代做法：
①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;
    }
};

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;
    }
};

中序遍历的迭代做法：
左中右：
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;
    }
};

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;
    }
};

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

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;
    }
};

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;
    }
};

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;
    }
};

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);
    }
};

最大深度、最小深度、完全二叉树的个数，这三个题有异曲同工之处。
递归+有返回值+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);
    }
};

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));
        }
    }
};

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;
    }
};