代码随想录刷题day14 | 二叉树理论基础、递归遍历、迭代遍历_二叉树的理论基础

1.二叉树理论基础

2.二叉树的递归遍历

递归的三要素

1. 确定递归函数的参数和返回值： 确定哪些参数需要处理，明确每次递归的返回值。
2. 确定终止条件： 没写终止条件或者终止条件写的不对，会造成栈溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。

144.二叉树的前序遍历

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& v){
        if(cur == nullptr)return;
        v.push_back(cur->val);
        traversal(cur->left, v);
        traversal(cur->right, v);
    }
    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

145.二叉树的后序遍历

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& v){
        if(cur == nullptr)return;
        traversal(cur->left, v);
        traversal(cur->right, v);
        v.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

94.二叉树的中序遍历

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& v){
        if(cur == nullptr)return;
        traversal(cur->left, v);
        v.push_back(cur->val);
        traversal(cur->right, v);
        
    }
    vector<int> inorderTraversal(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

---

3.二叉树的迭代遍历

144.二叉树的前序遍历

前序遍历使用栈实现
当根节点为空时，直接return；
当根节点不为空时，将根节点加入栈中，开始循环：
先取栈顶节点加入数组中，然后把这个节点的右节点和左节点依次加入栈中（加入的时候判断一下节点是否为空，空节点不入栈），注意次序（因为弹出时是先弹出左节点，符合前序遍历的顺序）！
最后返回结果数组。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if(root == nullptr)
            return res;
        
        st.push(root);//根节点入栈
        while(!st.empty()){//当栈不为空，就一直循环
            TreeNode* cur = st.top();
            st.pop();

            res.push_back(cur->val);//根节点加入数组
            if(cur->right) st.push(cur->right);//右节点入栈(空节点不入栈)
            if(cur->left) st.push(cur->left);//左节点入栈(空节点不入栈)
        }
        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:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if(root == nullptr)
            return res;
        
        st.push(root);//根节点入栈
        while(!st.empty()){//当栈不为空，就一直循环
            TreeNode* cur = st.top();
            st.pop();

            res.push_back(cur->val);//根节点加入数组
            if(cur->left) st.push(cur->left);//左节点入栈(空节点不入栈)
            if(cur->right) st.push(cur->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

94.二叉树的中序遍历

中序遍历由于访问的节点和要处理的节点不一致（先访问根节点，但是先push进数组的是一直向左遍历直到左孩子为空的节点），所以就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

• 当前节点不为空时，入栈，访问它的左孩子
• 当前节点为空时，从栈顶弹出元素加入数组中，访问它的右孩子

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;

        while(cur != nullptr || !stk.empty()){
            if(cur != nullptr){
                stk.push(cur);
                cur = cur->left;
            }else{//当cur为空时，从栈顶弹出元素
                cur = stk.top();
                stk.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
21

---

4.二叉树的统一迭代法

下次刷题时再填这个坑~