【算法专题】二叉树中的深搜(DFS)

深搜

深度优先遍历（DFS，全称为 Depth First Traversal），是我们树或者图这样的数据结构中常用的?种遍历算法。这个算法会尽可能深的搜索树或者图的分支，直到一条路径上的所有节点都被遍历完毕，然后再回溯到上一层，继续找?条路遍历。

在二叉树中，常见的深度优先遍历为：前序遍历、中序遍历以及后序遍历。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。并且前中后序三种遍历的唯一区别就是访问根节点的时机不同，在做题的时候，选择一个适当的遍历顺序，对于算法的理解是非常有帮助的。

1. 计算布尔二叉树的值

题目链接 -> Leetcode -2331.计算布尔二叉树的值

Leetcode -2331.计算布尔二叉树的值

题目：给你一棵 完整二叉树 的根，这棵树有以下特征：

叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
计算 一个节点的值方式如下：

如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。
完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。

示例 1：
输入：root = [2, 1, 3, null, null, 0, 1]
输出：true
解释：上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ，所以我们返回 true 。

示例 2：
输入：root = [0]
输出：false
解释：根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

• 树中节点数目在[1, 1000] 之间。
• 0 <= Node.val <= 3
• 每个节点的孩子数为 0 或 2 。
• 叶子节点的值为 0 或 1 。
• 非叶子节点的值为 2 或 3 。

思路：通过判断节点的值来做不同的操作，如果节点的值为1或0，说明是叶子节点，返回true/false；如果节点值是2，那么返回它的左子树 || 右子树；如果节点值是3，返回它的左子树 && 右子树。

代码如下：

		/**
		 * 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:
		    bool evaluateTree(TreeNode* root)
		    {
		        if (root->val == 1) return true;
		        if (root->val == 0) return false;
		
		        if (root->val == 2) return evaluateTree(root->left) || evaluateTree(root->right);
		        return evaluateTree(root->left) && evaluateTree(root->right);
		    }
		};

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

题目链接 -> Leetcode -129.求根节点到叶节点数字之和

Leetcode -129.求根节点到叶节点数字之和

题目：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：
输入：root = [1, 2, 3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：
输入：root = [4, 9, 0, 5, 1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

• 树中节点的数目在范围[1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

思路：
在前序遍历的过程中，我们可以往左右子树传递信息，并且在回溯时得到左右子树的返回值。递归函数可以帮我们完成两件事：

1. 将父节点的数字与当前节点的信息整合到?起，计算出当前节点的数字，然后传递到下?层进行递归；
2. 当遇到叶子节点的时候，就不再向下传递信息，而是将整合的结果向上一直回溯到根节点。

在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

代码如下：

		/**
		 * 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 ret = 0;
		
		    void dfs(TreeNode* root, int sum)
		    {
		        if(root->left == nullptr && root->right == nullptr) 
		        {
		            ret += sum;
		            return;
		        }
		
		        if(root->left) dfs(root->left, sum * 10 + root->left->val);
		        if(root->right) dfs(root->right, sum * 10 + root->right->val);
		    }
		
		    int sumNumbers(TreeNode* root) 
		    {
		        dfs(root, root->val);
		        return ret;
		    }
		};

3. 二叉树剪枝

题目链接 -> Leetcode -814.二叉树剪枝

Leetcode -814.二叉树剪枝

题目：给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：
输入：root = [1, null, 0, 0, 1]
输出：[1, null, 0, null, 1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例 2：
输入：root = [1, 0, 1, 0, 0, 0, 1]
输出：[1, null, 1, null, 1]

示例 3：
输入：root = [1, 1, 0, 1, 1, 0, 1, 0]
输出：[1, 1, 0, 1, 1, null, 1]

提示：

• 树中节点的数目在范围[1, 200] 内
• Node.val 为 0 或 1

思路：
如果我们选择从上往下删除，我们需要收集左右子树的信息，这可能导致代码编写相对困难。然而，通过观察我们可以发现，如果我们先删除最底部的叶子节点，然后再处理删除后的节点，最终的结果并不会受到影响。因此，我们可以采用后序遍历的方式来解决这个问题。在后序遍历中，我们先处理左子树，然后处理右子树，最后再处理当前节点。在处理当前节点时，我们可以判断其是否为叶子节点且其值是否为 0，如果满足条件，我们可以删除当前节点。

• 需要注意的是，在删除叶子节点时，其父节点很可能会成为新的叶子节点。因此，在处理完子节点后，我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因（后序遍历首先遍历到的一定是叶子节点）。
• 通过使用后序遍历，我们可以逐步删除叶子节点，并且保证删除后的节点仍然满足删除操作的要求。这样，我们可以较为方便地实现删除操作，而不会影响最终的结果。
• 若在处理结束后所有叶子节点的值均为 1，则所有子树均包含 1，此时可以返回。

代码如下：

		/**
		 * 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) 
		    {
		        if(root == nullptr) return nullptr;
		        
		        root->left = pruneTree(root->left);
		        root->right = pruneTree(root->right);
		
		        if(root->val == 0 && root->left == nullptr && root->right == nullptr) 
		        {
		            delete root;
		            root = nullptr;
		        }
		
		        return root;
		    }
		};

4. 验证二叉搜索树

题目链接 -> Leetcode -98.验证二叉搜索树

Leetcode -98.验证二叉搜索树

题目：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2, 1, 3]
输出：true

示例 2：
输入：root = [5, 1, 4, null, null, 3, 6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：
树中节点数目范围在[1, 10^4] 内

• -2^31 <= Node.val <= 2^31 - 1

思路：如果一棵树是二叉搜索树，那么它的中序遍历的结果一定是一个严格递增的序列。因此，我们可以初始化一个无穷小的全区变量，用来记录中序遍历过程中的前驱结点。那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下一层的递归中。

		/**
		 * 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 {
		    long prev = LONG_MIN;
		
		public:
		    bool isValidBST(TreeNode* root) 
		    {
		        if(root == nullptr) return true;
		
		        bool Left = isValidBST(root->left);
		
		        if(!Left) return false; // 剪枝
		
		        if(root->val <= prev) return false; //剪枝
		        prev = root->val;  
		
		        bool Right = isValidBST(root->right);
		
		        return Left && Right;
		    }
		};

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

题目链接 -> Leetcode -230.二叉搜索树中第K小的元素

Leetcode -230.二叉搜索树中第K小的元素

题目：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：
输入：root = [3, 1, 4, null, 2], k = 1
输出：1

示例 2：
输入：root = [5, 3, 6, 2, 4, null, null, 1], k = 3
输出：3

提示：
树中的节点数为 n 。

• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

思路：我们可以根据中序遍历的过程，只需扫描前 k 个结点即可；因此，我们可以创建一个全局的计数器 count，将其初始化为 k，每遍历一个节点就将 count- -；直到某次递归的时候，count 的值等于 1，说明此时的结点就是我们要找的结果。

		/**
		 * 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 
		{
		    int ret, count;
		public:
		    void dfs(TreeNode* root)
		    {
		        if(root == nullptr || count == 0) return;
		        dfs(root->left);
		
		        count--;
		        if(count == 0) ret = root->val;
		
		        dfs(root->right);
		    }
		
		    int kthSmallest(TreeNode* root, int k) 
		    {
		        count = k, ret = 0;
		        dfs(root);
		        return ret;
		    }
		};

6. 二叉树的所有路径

题目链接 -> 添加链接描述

Leetcode -257.二叉树的所有路径

题目：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [1, 2, 3, null, 5]
输出：[“1->2->5”, “1->3”]

示例 2：
输入：root = [1]
输出：[“1”]

提示：
树中节点的数目在范围[1, 100] 内

• 100 <= Node.val <= 100

思路：路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加入到路径中，如果该节点为叶子节点，将路径存储到结果中。否则，将 “->” 加入到路径中并递归遍历该节点的左右子树。定义一个结果数组，进行递归。递归具体实现方法如下：

1. 如果当前节点不为空，就将当前节点的值加入路径 str 中，否则直接返回；
2. 判断当前节点是否为叶子节点，如果是，则将当前路径加入到所有路径的存储数组 ret 中；
3. 否则，将当前节点值加上 “->” 作为路径的分隔符，继续递归遍历当前节点的左右子节点。
4. 返回结果数组

注意：我们可以只使用一个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中的当前节点移除，以回到上一个节点。

代码如下：

		/**
		 * 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 
		{
		    vector<string> ret;
		public:
		    void dfs(TreeNode* root, string str)
		    {
		        if(root->left == nullptr && root->right == nullptr) ret.push_back(str);
		
		        if(root->left)  dfs(root->left, str + ("->" + (to_string(root->left->val))));
		        if(root->right) dfs(root->right, str + ("->" + (to_string(root->right->val))));
		    }
		    
		    vector<string> binaryTreePaths(TreeNode* root) 
		    {
		        string str = to_string(root->val);
		        dfs(root, str);
		
		        return ret;
		    }
		};