政子的博客

技术|学习|随笔

二叉树相关知识点总结

二叉树的定义

1
2
3
4
5
6
7
8
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) {}
};

二叉树的遍历

遍历中的“前”、“中”、“后”序指的是访问根节点是在访问孩子节点之前、之中还是之后。

前序遍历

题目链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

递归解法

在所有遍历的递归解法中，需要注意的只有当遇到节点为空的时候需要 return 就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
    vector<int> result;

    void doTraversal(TreeNode* t) {
        if (t == nullptr) {
            return;
        }

        this->result.push_back(t->val);
        doTraversal(t->left);
        doTraversal(t->right);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        doTraversal(root);

        return this->result;
    }
};

迭代解法1

使用一个栈作为辅助，如果有左孩子，不断访问左孩子并将其进栈，然后再去考虑右孩子。

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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        
        if (root == nullptr) return result;

        stack<TreeNode*> s;
        TreeNode* t = root;

        while (!s.empty() || t != nullptr) {
            while(t != nullptr) {
                result.push_back(t->val);
                s.push(t);
                t = t->left;
            }
            t = s.top();
            s.pop();
            t = t->right;
        }

        return result;
    }
};

迭代解法2

使用一个辅助栈，先访问当前根节点，因为栈是后进先出，所以然后先将右孩子进栈，再将左孩子进栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;

        if (root == nullptr) return result;

        stack<TreeNode*> s;
        TreeNode* t;

        s.push(root);   
        while (!s.empty()) {
            t = s.top();
            s.pop();
            result.push_back(t->val);
            if (t->right != nullptr) s.push(t->right);
            if (t->left != nullptr) s.push(t->left);
        }

        return result;
    }
};

中序遍历

题目链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    vector<int> result;

    void doTraversal(TreeNode* t) {
        if (t == nullptr) return;
        doTraversal(t->left);
        this->result.push_back(t->val);
        doTraversal(t->right);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        doTraversal(root);

        return result;
    }
};

迭代解法1

和前序遍历的迭代解法 1 类似，只是访问根节点的实际从将左孩子压入栈变成了在出栈的时候。

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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;
        
        stack<TreeNode*> s;
        TreeNode* t = root;

        while (!s.empty() || t != nullptr ) {
           while(t != nullptr) {
               s.push(t);
               t = t->left;
           }
           t = s.top();
           result.push_back(t->val);
           s.pop();
           t = t->right;
        }

        return result;
    }
};

迭代解法2

还有一种只是用一层循环的解法：

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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;
        
        stack<TreeNode*> s;
        TreeNode* t = root;

        while (!s.empty() || t != nullptr ) {
            if (t != nullptr) {
                s.push(t);
                t = t->left;
            } else {
                t = s.top();
                result.push_back(t->val);
                s.pop();
                t = t->right;
            }
        }

        return result;
    }
};

后序遍历

题目链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    vector<int> result;

    void doTraversal(TreeNode* t) {
        if (t == nullptr) return;
        doTraversal(t->left);
        doTraversal(t->right);
        this->result.push_back(t->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        doTraversal(root);

        return this->result;
    }
};

迭代解法1

思路为拆解并用栈模拟递归，但是一个栈不足以保存递归的所有信息，所以用了两个栈

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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;

        stack<TreeNode*> s, h;
        TreeNode* t = root;

        while (!s.empty() || t != nullptr) {
            if (t != nullptr) {
                s.push(t);
                t = t->left;
            } else {
                t = s.top();
                if (!h.empty() && t == h.top()) {
                    result.push_back(t->val);
                    h.pop();
                    s.pop();
                    t = nullptr;
                } else if (t->right != nullptr) {
                    h.push(t);
                    t = t->right;
                } else {
                    result.push_back(t->val);
                    s.pop();
                    t = nullptr;
                }
            }
        }

        return result;
    }
};

迭代解法2

后序遍历需要使用双栈法，使用第一个栈做类似前序遍历的操作（只是这里访问左孩子需要在右孩子之前），使用第二个栈将前序遍历的操作进行逆序。最后将第二个栈的内容输出。

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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;

        stack<TreeNode*> s;
        stack<int> h;
        TreeNode* t;

        s.push(root);
        while (!s.empty()) {
            t = s.top();
            s.pop();
            h.push(t->val);

            if (t->left != nullptr) s.push(t->left);
            if (t->right != nullptr) s.push(t->right);
        }

        while (!h.empty()) {
            result.push_back(h.top());
            h.pop();
        }

        return result;
    }
};

层序遍历

题目链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

使用队列进行按照从上到下从左到右的顺序进行迭代，每访问到一个节点就去将它的左右孩子加入队列之中。

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;

        int this_level_count = 1;
        int next_level_count = 0;
        queue<TreeNode*> q;
        TreeNode* t;

        q.push(root);
        result.push_back(vector<int>());
        while (!q.empty()) {
            t = q.front();
            q.pop();
            result.back().push_back(t->val);
            if (t->left != nullptr) {
                q.push(t->left);
                next_level_count++;
            }
            if (t->right != nullptr) {
                q.push(t->right);
                 next_level_count++;
            }
            
            if (--this_level_count == 0) {
                this_level_count = next_level_count;
                next_level_count = 0;
                if (!q.empty()) result.push_back(vector<int>());
            }
        }

        return result;
    }
};

二叉树的重建

从前序遍历和中序遍历恢复二叉树

题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

递归解法

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
class Solution {
private:
    TreeNode* build(
        vector<int>& preorder,
        vector<int>& inorder,
        int pre_start,
        int pre_end,
        int in_start,
        int in_end
    ) {
        if (pre_start > pre_end || in_start > in_end) return nullptr;

        TreeNode* root = new TreeNode(preorder[pre_start]);
        if (pre_start == pre_end) return root;

        int left_num = 0;
        while (preorder[pre_start] != inorder[in_start + left_num]) left_num++;

        root->left = build(
            preorder,
            inorder,
            pre_start + 1,
            pre_start + left_num,
            in_start,
            in_start + left_num - 1
        );
        root->right = build(
            preorder,
            inorder,
            pre_start + left_num + 1,
            pre_end,
            in_start + left_num + 1,
            in_end
        );

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) return nullptr;

        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

从前序遍历和后续遍历恢复二叉树

题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

递归解法

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
class Solution {
    TreeNode* build(
        vector<int>& inorder,
        vector<int>& postorder,
        int in_start,
        int in_end,
        int post_start,
        int post_end
    ) {
        if (in_start > in_end || post_start > post_end) return nullptr;

        TreeNode* root = new TreeNode(postorder[post_end]);
        if (in_start == in_end) return root;

        int right_num = 0;
        while (postorder[post_end] != inorder[in_end - right_num]) right_num++;

        root->left = build(
            inorder,
            postorder,
            in_start,
            in_end - right_num - 1,
            post_start,
            post_end - right_num - 1
        );
        root->right = build(
            inorder,
            postorder,
            in_end - right_num + 1,
            in_end,
            post_end - right_num,
            post_end - 1
        );

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return nullptr;

        return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
};