面试中经常会考察诸如此类问题
二叉树的所有路径 https://leetcode-cn.com/problems/binary-tree-paths/
判断二叉树是否平衡 https://leetcode-cn.com/problems/balanced-binary-tree/
等等类似的二叉树相关的问题。遇到此类问题之前我经常是看到题目很懵逼、完全无从下手、纵然 leetcode 上标注了一个大大的 easy 字样，但是我还是不知道题目考察的是什么。 直到研究了一下此类题目的共性、发现此类题目实际考察的就是 【递归】【深搜 DFS】【回溯法】
递归 Recursion
递归函数是程序的一种实现方式、也就是函数进行了自我调用
递归算法: 即大问题的结果依赖于小问题的结果，于是先用递归函数求解小问题
一般我们说递归的时候，大部分都是在说递归函数而不是递归算法
深度优先搜索 DFS
回溯 BackTracing
到这里我们了解了 通常二叉树问题考察 DFS、那么实际在写 DFS 程序的时候都有哪几种方式呢？
遍历法
分治法
好了、有了理论基础、我们里看看具体的题目如何实现。如何体现这些思路的。
首先通过两个例子来了解什么是回溯。
题目 1： 查找二叉树中所有的节点
public void findNodes(TreeNode node,List<TreeNode> nodes){ if(node == null){ return; } nodes.add(node); findNodes(node.left,nodes); findNodes(node.right,nodes); //这个题目无回溯}
复制代码
题目 2： 给定一个二叉树，返回所有从根节点到叶子节点的路径。
public void findPaths(TreeNode node,List<String> path,List<List<String>> paths){ if (node == null){ return; } if(node.left == null && node.right == null){ paths.add(new ArrayList<>(path));//此处一定使用 new ArrayList 拷贝 path的副本给到paths return; } if(node.left != null){ path.add(node.left.vale); findPaths(node.left,path,paths); path.remove(path.size() - 1); } if(node.right != null){ path.add(node.right.vale); findPaths(node.right,path,paths); path.remove(path.size() - 1); //此处需要回溯操作，也就是在调用之前设么值，调用之后需要让他恢复回调用之前的值、这里的path需要删除最后一个值 //注意此处path.remove(path.size()-1) 做回溯操作 }}
复制代码
题目 2 的解法一中，需要对 path 进行回溯操作。
还有一种不需要回溯操作的写法。利用 String 的不可变特性来实现的
public void findPath(TreeNode node,String path,List<String> paths){ if(node == null){ return; } if(node.left == null && node.right == null){ paths.add(path); return; } if(node.left != null){ findPaths(node.left,path + "->" + node.left.vale,paths); } if(node.right != null){ //这里不需要回溯的原因是、当进行下一层级递归的时候、传递的path是新创建的path、所以当下一层递归调用方法结束的，心传递的path就会销魂，不会影响 //当前层级的path变量。 findPaths(node.right,path + "->" + node.right.vale,paths); }}
复制代码
DFS 的两种具体写法 【遍历法】【分治法】
遍历法类似于一个小人拿着一个笔记本走遍所有的节点。上面我们演示的回溯的两个题目都是遍历法的应用。
遍历法通常会用到一个全局变量或者共享参数
分治法
通常将利用 return value 记录子问题结果，二叉树上的分治法本质上也是在做遍历。
public 返回结果类型 divideConquer(TreeNode root){ if(root == null){ 处理空树应该返回的结果 }// if(root.left == null && root.right == null){ //处理叶子应该返回的结果 //如果叶子的返回结果可以通过两个空节点的返回结果得到就可以省略这一段代码 //} 左子树返回结果 = divideConquer(root.left); 右子树返回结果 = divideConquer(root.right); 整棵树的结果 = 按照一定的方法合并左右子树的结果。 return 整棵树的结果;}
复制代码
举个例子
判断一个二叉树是否平衡、
平衡二叉树定义： 任意节点左右子树高度之差不超过 1
https://leetcode-cn.com/problems/check-balance-lcci/
//定义 求出 root 为根的子树是否是平衡树且返回高度//这里为什么要定义成这样？//首先肯定要定义返回结果: 是否是平衡二叉树 boolean类型//紧接着考虑如果左右子树的平衡性都已知的情况、如何得出整棵树的平衡性呢、能否只通过左右子树的平衡性得出整颗树的平衡性呢、这里考虑了一下//发现不能，那么还需什么信息才能定义，这里还需要左右子树的高度信息。从而才能判断出此棵树的平衡心。故返回需要添加高度信息。public Result divideConquer(TreeNode root){ //出口 空树的时候，返回 isBalaced = true,height = 0; if(root == null){ return new Result(true,0); } //拆解： 拆解到左右两边得到左右子树的平衡信息和高度信息。 Result leftResult = divideConquer(root.left); Result rightResult = divideConquer(root.right); int height = Math.max(leftResult.height,rightResult.height) + 1; boolean isBalanced = true; if(!leftResult.isBalaced || !rightResult.isBalanced()){ isBalanced = false; } if(Math.abs(leftResult.height - rightResult.height) > 1){ isBalanced = false; } return new Result(isBalanced,height); }
复制代码
其实分治法不单用在二叉树场景上、只要可以分成几个子问题、子问题的结果处理完成之后、在子问题解的基础之上计算当前问题的解。这种应用场景就是针对数组上的归并排序。
public static void mergeSort(int[] arrays, int start, int end, int[] temp) {if (start >= end) {return;}//区间分治法的 int middle = (start + end) / 2;//divide 拆解过程： 左边部分的 mergeSortmergeSort(arrays, start, middle, temp);//divide 拆解过程： 右边部分的 mergeSortmergeSort(arrays, middle + 1, end, temp);//conquer 过程、merge(arrays, start, end, temp);}
private static void merge(int[] arrays, int start, int end, int[] temp) { if (start >= end) { return; } int middle = (start + end) / 2; int leftIndex = start; int rightIndex = middle + 1; int index = leftIndex; while (leftIndex <= middle && rightIndex <= end) { if (arrays[leftIndex] < arrays[rightIndex]) { temp[index++] = arrays[leftIndex++]; } else { temp[index++] = arrays[rightIndex++]; } } while (leftIndex <= middle) { temp[index++] = arrays[leftIndex++]; } while (rightIndex <= end) { temp[index++] = arrays[rightIndex++]; } //注意这里是 i = start for (int i = start; i <= end; i++) { arrays[i] = temp[i]; }
}
复制代码
评论