Leetcode 刷题笔记——树

Posted on In Symbols count in article: 3.9k Reading time ≈ 4 mins.

总结一下二叉树的各种遍历操作。

144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

方法一：递归

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

方法二：栈

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

94. 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> res;
    
    vector<int> inorderTraversal(TreeNode* root) {
        if (root != nullptr) {
            inorderTraversal(root->left);
            res.push_back(root->val);
            inorderTraversal(root->right);
        }
        return res;
    }
};

方法二：栈

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

145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

方法一：递归

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

方法二：栈

首先依然和中序遍历一样，不断将左孩子入栈。不同的地方在于停下后，不能直接弹出栈顶节点，因为后序遍历要先访问右子树，最后才访问根节点。因此我们需要知道当前是从左子树回来的，还是从右子树回来的。为了解决这个问题，我们用变量 last 存储上一次访问的节点。如果当前节点的右孩子和 last 相同，则说明是从右子树回来的，那么就可以弹出当前节点并将其加入结果列表。

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
class Solution {
public:
    vector<int> res;
    
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* curr = root;
        TreeNode* last = nullptr;
        while (curr != nullptr || !s.empty()) {
            while (curr != nullptr) {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            if (curr->right == nullptr || curr->right == last) {
                res.push_back(curr->val);
                last = curr;
                s.pop();
                curr = nullptr;
            } else {
                curr = curr->right;
            }
        }
        return res;
    }
};

方法三：递归（转换为前序遍历）

我们发现前序遍历的顺序是 根 -> 左 -> 右 ，如果将代码中左右孩子压栈的顺序反过来，就变成了 根 -> 右 -> 左（和标准的前序遍历本质上是等价的），然后再把序列反转一下，就得到了后序遍历的顺序 左 -> 右 -> 根 。

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

102. 二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

方法一：递归（本质上还是先序遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> res;
    
    vector<vector<int>> levelOrder(TreeNode* root) {
        preorder(root, 0);
        return res;
    }

    void preorder(TreeNode* root, int level) {
        if (root != nullptr) {
            if (res.size() <= level)
                res.push_back({});
            res[level].push_back(root->val);
            preorder(root->left, level + 1);
            preorder(root->right, level + 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
class Solution {
public:
    vector<vector<int>> res;
    
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return res;

        queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        int qsize = q.size();
        while (!q.empty()) {
            res.push_back({});
            while (qsize--) {
                TreeNode* curr = q.front();
                q.pop();
                res[level].push_back(curr->val);
                if (curr->left != nullptr)
                    q.push(curr->left);
                if (curr->right != nullptr)
                    q.push(curr->right);
            }
            qsize = q.size();
            level++;
        }
        return res;
    }
};