[Algorithm][二叉树中的深搜][计算布尔二叉树的值][求根节点到叶节点数字之和][二叉树剪枝][验证二叉搜索树][二叉搜索树中第K小的元素][二叉树的所有路径] 详细讲解

---

1.计算布尔二叉树的值

1.题目链接

• 计算布尔二叉树的值

---

2.算法原理详解

• 题目理解：
  

• 流程：

  • 重复子问题 -> 函数头：
    • bool DFS(Node* root)
  • 只关心某一个子问题在做什么 -> 函数体实现
    • bool left = DFS(root->left
    • bool right = DFS(root->right)
    • 根据当前结点进行响应运算
  • 递归出口：叶子结点则返回
    • root->left == nullptr -> return root
      

---

3.代码实现

bool EvaluateTree(TreeNode* root) 
{
    // 函数出口
    if(root->left == nullptr)
    {
        return root->val;
    }

    auto left = evaluateTree(root->left);
    auto right = evaluateTree(root->right);

	return root->val == 2 ? left | right : left & right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

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

1.题目链接

• 求根节点到叶节点数字之和

---

2.算法原理详解

• 思路：前序遍历的过程中，可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值
  • 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递归
  • 当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点
  • 在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和
• 流程：
  • 重复子问题 -> 函数头：int DFS(TreeNode* root, int prevNum)
    • 返回值：当前子树计算的结果
    • 参数prevNum：父节点的数字
  • 只关心某一个子过程在做什么-> 函数体
    • 整合⽗节点的信息与当前节点的信息计算当前节点数字，并向下传递，在回溯时返回当前⼦树数字和
  • 递归出口：叶子节点
    

---

3.代码实现

class Solution 
{
public:
    int sumNumbers(TreeNode* root) 
    {
        return DFS(root, 0);
    }

    int DFS(TreeNode* root, int prevSum)
    {
        if(root == nullptr)
        {
            return 0;
        }

        prevSum = prevSum * 10 + root->val;

        if(root->left == nullptr && root->right == nullptr)
        {
            return prevSum;
        }

        return DFS(root->left, prevSum) + DFS(root->right, prevSum);
    }
};
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

---

3.二叉树剪枝

1.题目链接

• 二叉树剪枝

---

2.算法原理详解

• 通过决策树，抽象出递归的三个核心问题
  • 函数头：Node* DFS(Node* root)
  • 函数体：
    1. 处理左子树
    2. 处理右子树
    3. 判断
  • 递归出口：root == nullptr
    

---

3.代码实现

TreeNode* PruneTree(TreeNode* root) 
{
    if(root == nullptr)
    {
        return nullptr;
    }

    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);

    if(!root->val && !root->left && !root->right)
    {
        delete root; // 防止内存泄漏
        root = nullptr;
    }

    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

4.验证二叉搜索树

1.题目链接

• 验证二叉搜索树

---

2.算法原理详解

• 通过此题可以感受出「全局变量的优势」「回溯」「剪枝」
• 思路：如果⼀棵树是⼆叉搜索树，那么它的中序遍历的结果⼀定是⼀个严格递增的序列
  • 可以初始化⼀个⽆穷⼩的全局变量，⽤来记录中序遍历过程中的前驱结点
  • 那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下⼀层的递归中
• 方法一：依次执行以下判断
  • 左子树是不是二叉搜索树
  • 当前节点是否复合二叉搜索树的定义
  • 右子树是不是二叉搜索树
• 方法二：法一 + 剪枝
  

---

3.代码实现

// v1.0 暴力判断
class Solution 
{
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) 
    {
        if(root == nullptr)
        {
            return true;
        }

        // 判断左子树
        bool left = isValidBST(root->left);

        // 判断自己
        bool cur = false;
        if(root->val > prev)
        {
            cur = true;
        }
        prev = root->val;

        // 判断右子树
        bool right = isValidBST(root->right);

        return left && right && cur;
    }
};
------------------------------------------------------------------------
// v2.0 剪枝
class Solution 
{
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) 
    {
        if(root == nullptr)
        {
            return true;
        }

        // 1.判断左子树
        bool left = isValidBST(root->left);
        if(!left) // 剪枝
        {
            return false;
        }

        // 2.判断自己
        bool cur = false;
        if(root->val > prev)
        {
            cur = true;
        }
        prev = root->val;

        if(!cur) // 剪枝
        {
            return false;
        }

        // 3.判断右子树
        bool right = isValidBST(root->right);

        return left && right && cur;
    }
};
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

---

5.二叉搜索树中第K小的元素

1.题目链接

• 二叉搜索树中第K小的元素

---

2.算法原理详解

• 通过此题可以感受出「全局变量的优势」「回溯」「剪枝」
• 思路：
  • 创建⼀个全局的计数器count，将其初始化为k，每遍历⼀个节点就将count--，直到某次递归的时候，count == 0，说明此时的结点就是要找的结果
  • 创建一个全局的ret，用于存储最终结果，简化返回值设计
    

---

3.代码实现

class Solution 
{
    int count, ret;
public:
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        DFS(root);
        return ret;
    }

    void DFS(TreeNode* root)
    {
        // 函数出口 + 剪枝
        if(root == nullptr || count == 0)
        {
            return;
        }

        DFS(root->left);

        if(--count == 0)
        {
            ret = root->val;
        }

        DFS(root->right);
    }
};
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

---

6.二叉树的所有路径

1.题目链接

• 二叉树的所有路径

---

2.算法原理详解

• 通过此题可以感受出「全局变量的优势」「回溯」「剪枝」
  • 全局变量：保存结果
  • 回溯：恢复现场，通常有两种做法
    • 全局变量
    • 函数传参(本题以它为主实现)
  • 剪枝：加快搜索过程(本题可有可无)
• 流程：
  • 函数头：void DFS(Node* root, string path)
  • 函数体：
    • if(root != nullptr)，就将当前节点的值加⼊路径path中，否则直接返回
    • 判断当前节点是否为叶⼦节点
      • 如果是，则将当前路径加⼊到所有路径的存储数组ret中
      • 否则，将当前节点值加上"->"作为路径的分隔符，继续递归遍历当前节点的左右⼦节点
  • 递归出口：if(root == nullptr) return;

---

3.代码实现

class Solution 
{
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        DFS(root, "");
        return ret;
    }

    // 参数path实现回溯
    void DFS(TreeNode* root, string path)
    {
        path += to_string(root->val);

        // 叶子结点 + 函数出口
        if(!root->left && !root->right)
        {
            ret.push_back(path);
        }

        path += "->";

        // 非叶子结点 + 剪枝
        if(root->left)
        {
            DFS(root->left, path);
        }

        if(root->right)
        {
            DFS(root->right, path);
        }
    }
};
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