【递归、搜索和回溯算法】专题二 ：二叉树中的深搜

二叉树中的深搜 

---

深度优先遍历（DFS）：一种沿着树或图的深度遍历节点的算法，尽可能深地搜索树或图的分支，如果一条路径上的所有结点都被遍历完毕，就会回溯到上一层，继续找一条路遍历。

在二叉树中，常见的深度优先遍历：前序遍历、中序遍历、后序遍历，树的定义本身就是递归的定义。

搜索题型 

1.计算布尔二叉树

2331. 计算布尔二叉树的值 - 力扣（LeetCode）

 题目说了只有叶子结点本身才是布尔类型的值，其他的节点都需要进行运算后才是布尔类型的值。

面对这道题，首先我们就需要知道根结点左右两边的布尔值，但是要计算左右两边的又需要它们左右两边的布尔值，就需要用到递归算法来计算左右两边的布尔值。

     递归三步      

• 函数头

boolean evaluateTree(TreeNode root)

直接传入一个节点的参数就可以；

• 函数体

先访问左子树，再访问右子树，最后返回当前的节点是2还是3后计算后的布尔值（是2将左右子树通过逻辑或计算，是3就通过逻辑与计算）。【注：逻辑或（|）：如果左右子树全为假该节点就为假，如果左右子树中有一个为真那就该节点为真。逻辑与（&）：如果左右子树全为真该节点就为真，如果左右子树中有一个为假那就该节点为假】

• 递归出口

当遇到叶子结点时，如果该节点的值为0就返回false，相反不是0就返回true；

    编写代码    

    public boolean evaluateTree(TreeNode root) {if(root.left == null && root.right == null){return root.val == 0 ? false : true;}boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? left | right : left & right;}

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

 129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

首先我们把dfs这个方法看作一个黑盒，相信他一定可以得到我们想要的结果。每走到一个节点我们都需要前一个结点的值，这就是关键，我们要知道递归的子问题在做什么。

将上面例子进行分析，当我们到3这个节点时我们要拿到13，所以返回类型需要一个int类型来接收，然后传给访问左节点再访问右节点。每一个交界点都需要将后面所有的结果返回交界点，让交界点负责再往回送最后到头节点，所以在这过程中需要两个变量一个用来记录当前节点之和，一个用来记录左右节点返回的值之和，当左右节点为空时就返回记录当前节点的值，如果不为空那就返回记录左右节点的返回的值之和。

     递归三步      

• 函数头

int dfs(TreeNode root, int presum)

• 函数体

首先需要更新当前节点之和presum = 10*presum + root.val，将更新后的节点之和传个左右子树（要判断是否有左右子树），这里还需要用到回溯，如果该节点的左右子树已经求完还需要往回找到交界节点，继续左右子树求和返回；

• 递归出口

如果是叶子结点那就直接返回当前节点之和presum；

    编写代码    

    public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int prenum){prenum = prenum*10+root.val;if (root.left == null && root.right == null){return prenum;}int ret = 0;if (root.left != null){ret += dfs(root.left, prenum);}if (root.right != null){ret += dfs(root.right, prenum);}return ret;}

3.二叉树的剪枝

 814. 二叉树剪枝 - 力扣（LeetCode）

如果这颗子树的所有结点的值全为0那就可以将这个子树剪掉。所以并不是将所有的0都剪掉。 

要想找到全为0的子树，那就需要知道左右子树的所有信息，如果我们遍历到叶子结点时该节点的值为0那我们就剪去这个叶子结点返回上一层，那怎么剪呢？如果是叶子结点那就返回null。所以返回值需要进行接收，这样函数头就设计好了。

     递归三步      

• 函数头

TreeNode pruneTree(TreeNode root)，把该结点所在的左右子树中，所有包含0的子树移除移完后；

• 函数体

先访问左子树，再访问右子树，如果叶子结点的值为0就返回空指针，不是空返回当前节点。

• 递归出口

如果该节点为空就返回空指针

    编写代码    

    public TreeNode pruneTree(TreeNode root) {if (root == null){return null;}root.left = pruneTree(root.left);root.right = pruneTree(root.right);if (root.left == null && root.right == null && root.val == 0){return null;}else{return root;}}

4.验证二叉搜索树

 98. 验证二叉搜索树 - 力扣（LeetCode）

二叉搜索树：左子树的值要小于根节点的值，右子树的值要大于根结点的值，一棵树中每一棵子树都满足该定义的树就是二叉搜索树；

我们要借助中序遍历是一个有序的这个结论，就可以通过全局变量来比较每一个结点，每比较完一次就将该节点的值给全局变量，这样只要一出现不合理的就返回false。但是如果我们再中途中发现了false，我们就不再需要继续往后进行遍历了，直接剪枝。只有当左右子树以及根结点都满足true那就返回true。【注：设置全局变量时我们需要一个最小值，题目范围是int的最小最大，但是如果二叉树中存在最小值时，那就不能比较了，所以我们设置全局变量时用long的最小值】

     递归三步      

• 函数头

boolean isValidBST(TreeNode root)，需要一个布尔返回值辨别是否符合定义，还需要一个当前节点；

• 函数体

首先先判断左子树，如果存在false直接剪枝，再判断当前结点，如果存在false直接剪枝，最后盘算右子树，最后返回左根右子树的逻辑与值；

• 递归出口

如果当前节点为空时返回true

    编写代码    

    long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null){return true;}boolean left = isValidBST(root.left);if (left == false){return false;}boolean cur = false;if (pre < root.val){cur = true;pre = root.val;}if (cur == false){return false;}boolean right = isValidBST(root.right);return left && cur && right;}

5.二叉树中第k小的元素

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

只要设计有序的二叉树，一般都需要用到中序遍历，再结合上一题中的全局变量那么这道题就跟简单了，做法与上一题的验证二叉搜索树相像。

我们可以设置全局变量来计数，在通过全局变量来记录题目要求的第k小的元素，先遍历左子树，直到到达最小值，开始计数如果count值等于题目已知的k，那么用ret记录下来并且count加1（这里count为什么要加1？因为如果不加那么下一次再比较时还是相等那就不符合题意），返回ret即可但是如果不是那么count也要加1，然后再遍历右子树，最后返回记录值ret；

     递归三步      

• 函数头

int kthSmallest(TreeNode root, int k)，需要返回一个第k小值，还需要一直知道k的值，以及当前节点

• 函数体

同样先左子树，当前节点判断，再右子树（中序遍历）

• 递归出口

如果当前节点为空，那就返回0；

    编写代码    

    //全局变量public int count = 1;public int ret = 0;public int kthSmallest(TreeNode root, int k) {if (root == null){return 0;}kthSmallest(root.left, k);if (count == k) {ret = root.val;count++;return ret;} else {count++;}kthSmallest(root.right, k);return ret;}

6.二叉树所有路径 

257. 二叉树的所有路径 - 力扣（LeetCode）

我们需要一个全局变量来记录链表，每完成一条路经就将这条路径转成字符串添加到链表中。 

开始时我们会从根节点开始遍历记录所有分支，直到叶子结点为结束这就是一条完整的路径，我们可以用字符串来接收。每遍历一个新的结点我们都先把原先结点的记录都保存新的字符串中，然后再将该节点放进新字符串中（对于这种时不时添加字符，如果用String那就不好添加，String很难改变原本结构，所以我们可以用StringBuffer来进行随意添加操作），先记录在访问后序的结点。如果当前节点已经是叶子节点了那就将新建的字符串添加到链表中再结束这条路经，但如果不是那就添加一个箭头再进行左子树和右子树的操作。

     递归三步      

• 函数头

void dfs(TreeNode root, StringBuffer _path)，需要一个字符串来记录路径。

• 函数体

创建一个新的StringBuffer记录原先字符串再添加当前节点值，如果是叶子节点结束，不是那就继续左子树右子树递归

• 递归出口

当遇到叶子结点那就添加结束返回；

    编写代码    

    List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root, new StringBuffer());return ret;}public void dfs(TreeNode root, StringBuffer _path) {StringBuffer path = new StringBuffer(_path);path.append(Integer.toString(root.val));if (root.left == null && root.right == null) {ret.add(path.toString());return ;} else {path.append("->");if (root.left != null) {dfs(root.left, path);}if (root.right != null) {dfs(root.right, path);}}}