LCR047-LCR051二叉树的深度优先搜索

剑指offer（专项突破版）8.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
/**
 * 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:
    void preorder(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        res.push_back(root->val);
        preorder(root->left);
        preorder(root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        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
26
27
28
29
30
/**
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        TreeNode* cur = root;
        while(cur || !stack.empty()){
            while(cur){
                res.push_back(cur->val);
                stack.push(cur);
                cur = cur->left;
            }
            cur = stack.top();
            stack.pop();
            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
22
23
24
25
26
27
/**
 * 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:
    void inorder(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        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
26
27
28
29
30
/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        TreeNode* cur = root;
        while(cur || !stack.empty()){
            while(cur){
                stack.push(cur);
                cur = cur->left;
            }
            cur = stack.top();
            stack.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
22
23
24
25
26
27
/**
 * 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:
    void postorder(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(root, res);
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        TreeNode* cur = root;
        TreeNode* prev = NULL;
        while(cur || !stack.empty()){
            while(cur){
                stack.push(cur);
                cur = cur->left;
            }
            // 如果当前结点有右子树且没遍历过，则遍历右子树
            cur = stack.top();
            if(cur->right && cur->right != prev){
                cur = cur->right;
            }
            // 否则将当前结点弹出
            else{
                stack.pop();
                res.push_back(cur->val);
                prev = cur;
                cur = NULL;
            }
        }
        return res;
    }
};

LCR047.二叉树剪枝

分析

如果用后序遍历的顺序遍历到某个节点，那么它的左右子树的节点一定已经遍历过了。每遍历到一个节点，就要确定它是否有左右子树，如果左右子树都是空的，并且节点的值是0，那么也就可以删除这个节点。

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
/**
 * 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* pruneTree(TreeNode* root) {
        // 如果root为空
        if(!root){
            return root;
        }
        // 查看左右子树
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        // 如果左右子树都为空且当前结点为0
        if(!root->left && !root->right && root->val == 0){
            return NULL;
        }
        return root;
    }
};
  • 时间复杂度：递归函数pruneTree会遍历整棵树的每个节点，因此时间复杂度为O(n)。
  • 空间复杂度：递归调用pruneTree函数会消耗栈空间，其最大递归深度等于树的高度O(h)。

LCR047结果

LCR048.序列化和反序列化

分析

先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点，每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉树最适合序列化。如果采用前序遍历的顺序，那么二叉树的根节点最先序列化到字符串中，然后是左子树，最后是右子树。这样做的好处是在反序列化时最方便，从字符串中读出的第1个数值一定是根节点的值。

实际上，只把节点的值序列化到字符串中是不够的。首先，要用一个分隔符（如逗号）把不同的节点分隔开。其次，还要考虑如何才能在反序列化的时候构建不同结构的二叉树。如果节点是null则返回特殊字符串”＃”；否则生成一个字符串。

反序列化：由于把二叉树序列化成一个以逗号作为分隔符的字符串，因此可以根据分隔符把字符串分隔成若干子字符串，每个子字符串对应二叉树的一个节点。如果一个节点为null，那么它和”＃”对应；否则这个节点将和一个表示它的值的子字符串对应。

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
45
46
47
48
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root){
            return "#";
        }
        string left = serialize(root->left);
        string right = serialize(root->right);
        return to_string(root->val) + "," + left + "," + right;
    }
    // 辅助函数
    TreeNode* dfs(stringstream& ss){
        string str;
        getline(ss, str, ',');  // 从ss中读取一行，以','作为分隔符
        // 如果读取到"#"，表示空节点，返回nullptr
        if(str == "#"){
            return NULL;
        }
        // 创建当前节点
        TreeNode* root = new TreeNode(stoi(str));
        // 递归调用左右子树
        root->left = dfs(ss);
        root->right = dfs(ss);
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        // 使用stringstream处理字符串
        stringstream ss(data);
        // 递归调用辅助函数
        return dfs(ss);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
  • 时间复杂度：对于序列化部分，每个节点都被表示为一个字符串，并且对于每个节点，都递归地调用了左子树和右子树的序列化函数。因此，序列化函数的时间复杂度取决于二叉树的节点数，为 O(n)，其中 n 是二叉树中的节点数。对于反序列化部分，算法使用了递归，每次读取一个节点，然后递归地读取其左右子树。因此，反序列化函数的时间复杂度也是 O(n)，其中 n 是二叉树中的节点数。
    总体来说，这个算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数。
  • 空间复杂度：在序列化和反序列化函数中，我们递归会使用栈空间，故渐进空间复杂度为 O(n)。

LCR048结果

LCR049.求根节点到叶节点数字之和

分析

每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。如果这个节点还有子节点，就把这个值传下去继续遍历它的子节点。先计算到当前节点为止的路径表示的数字，再计算到它的子节点的路径表示的数字，这实质上就是典型的二叉树前序遍历。

路径的定义是从根节点开始到叶节点结束，因此只有遇到叶节点才返回路径表示的数字（代码中的变量path）。如果在遇到叶节点之前就结束的路径，由于不符合题目要求，因此应该返回0。

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
/**
 * 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:
    int dfs(TreeNode* root, int pathSum){
        if(!root){
            return 0;
        }
        // 更新当前路径的数字之和
        pathSum = pathSum * 10 + root->val;
        // 如果是叶子节点，则将当前路径的数字之和累加到总和中
        if(!root->left && !root->right){
            return pathSum;
        }
        // 继续遍历左右子树
        return dfs(root->left, pathSum) + dfs(root->right, pathSum);
    }
    
    int sumNumbers(TreeNode* root) {
        int pathSum = 0;
        return dfs(root, pathSum);
    }
};
  • 时间复杂度：O(n)，其中n是二叉树的节点个数。对每个节点访问一次。
  • 空间复杂度：O(n)，其中n是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为O(n)。

LCR049结果

LCR050.路径总和

分析

如果在路径上移动时把所有累加的节点值之和都保存下来，就容易知道是否存在从任意节点出发的值为给定sum的路径。当遍历到一个节点时，先累加从根节点开始的路径上的节点值之和，再计算到它的左右子节点的路径的节点值之和。这就是典型的前序遍历的顺序。

使用哈希表保存之前累加到的和，哈希表的键是累加的节点值之和，哈希表的值是每个节点值之和出现的次数。当遍历到一个节点时，就把当前的节点值累加到参数path。如果这个和之前出现过，则将出现的次数加1；如果这个和之前没有出现过，那么这是它第1次出现。然后更新哈希表map保存累加节点值之和path及出现的次数。程序回到节点的父节点时，也就是说，在函数结束之前需要将当前节点从路径中删除，从根节点到当前节点累加的节点值之和也要从哈希表map中删除。

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
/**
 * 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:
    int dfs(TreeNode* root, int targetSum, long path, unordered_map<long, int>& hash){
        if(!root){
            return 0;
        }
        // 更新当前路径和
        path += root->val;
        // 查找
        int count = (hash.count(path - targetSum)) ? hash[path-targetSum] : 0;
        if(hash.count(path)){
            hash[path]++;
        }
        else{
            hash[path] = 1;
        }
        count += dfs(root->left, targetSum, path, hash);
        count += dfs(root->right, targetSum, path, hash);
        hash[path]--;
        return count;
    }
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> hash;   // 定义哈希表，存储路径和及其出现的次数
        hash[0] = 1;                    // 没有节点时，和为0
        return dfs(root, targetSum, 0, hash);
    }
};

注意给定输入的范围可能会产生溢出，所以和的部分用long来表示。

LCR050结果

LCR051.二叉树中的最大路径和

分析

由于路径可能只经过左子树或右子树而不经过根节点，为了求得二叉树的路径上节点值之和的最大值，需要先求出左右子树中路径节点值之和的最大值（左右子树中的路径不经过当前节点），再求出经过根节点的路径节点值之和的最大值，最后对三者进行比较得到最大值。由于需要先求出左右子树的路径节点值之和的最大值，再求根节点，这看起来就是后序遍历。

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
/**
 * 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:
    int dfs(TreeNode* root, int& maxSum){
        if(!root){
            return 0;
        }
        // 递归计算左右子树的最大路径和，如果子树的最大路径和为负数，则置为0
        int leftSum = max(0, dfs(root->left, maxSum));
        int rightSum = max(0, dfs(root->right, maxSum));
        // 计算以当前节点为根的最大路径和（包含左右子树）
        int curMax = root->val + leftSum + rightSum;
        // 更新全局最大路径和
        maxSum = max(maxSum, curMax);
        // 返回以当前节点为根的子树中的最大路径和（只能选择左子树或右子树）
        return root->val + max(leftSum, rightSum);
    }
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        dfs(root, maxSum);
        return maxSum;
    }
};

LCR051结果

总结

[!WARNING]
对二叉树深度优先搜索的题目掌握得并不好，以后需要再练。

下面比较中序遍历、前序遍历和后序遍历这3种不同遍历算法的代码。它们的递归代码都很简单，只需要调整代码的顺序就能写出对应算法的代码。

它们的迭代代码也很类似，如它们都需要用到一个栈，而且代码的基本结构很相像，都有两个while循环并且它们的条件都一样。需要留意遍历当前节点的时机。前序遍历一边顺着指向左子节点的指针移动一边遍历当前的节点，而中序遍历和后序遍历则顺着指向左子节点的指针移动时只将节点放入栈中，并不遍历遇到的节点。只有当到达最左子节点之后再从栈中取出节点遍历。后序遍历最复杂，还需要保存前一个遍历的节点，并根据前一个遍历的节点是否为当前节点的右子节点来决定此时是否可以遍历当前的节点。

不管是哪种深度优先搜索算法，也不管是递归代码还是迭代代码，如果二叉树有n个节点，那么它们的时间复杂都是O（n）。如果二叉树的深度为h，那么它们的空间复杂度都是O（h）。在二叉树中，二叉树的深度h的最小值是log2（n+1），最大值为n。例如，包含7个节点的二叉树，最少只有3层（二叉树的第1层有1个节点，第2层有2个节点，第3层有4个节点），但最多可能有7层（二叉树中除了叶节点，其他每个节点只有1个子节点）。

算法笔记 > 树
#剑指Offer
LCR047-LCR051二叉树的深度优先搜索
http://example.com/2024/05/09/posts/LCR047/
作者
Xuan Yang
发布于
2024年5月9日
许可协议