1. LeetCode 513. 找树左下角的值
1.1 思路
- 运用迭代法层序遍历很简单，就最后一层第一个。以下讲解递归法
- 在这题只要我们求深度最大的叶子节点，就一定是在最后一行。
- 那么问题是最后一行怎么求第一个元素呢？这题前中后序都是可以的，“根左右”、“左根右”、“左右根”，因为这题没有“根节点”的处理逻辑的，只需要先遍历左即可，而不处理“根”那“左”就是第一个遍历的，那么一旦得到深度最大的节点，那优先遍历“左”，得到的就是最后一行第一个节点。
- 我们需要定义全局变量maxDepth记录最大深度，value记录节点的值
- 递归函数的参数和返回值：参数TreeNode，depth表示当前遍历的深度，因为操作的是全局变量，不用返回值
- 终止条件：遍历到叶子节点就是终止条件（left==null&&right==null）即左右孩子均为空，找到后就要比较判断了，depth是否比maxDepth大，如果大就更新maxDepth的值为depth，value更新为当前节点的数值。这步的操作只会记录到这一层第一个节点的值，因为depth和maxDepth的判断只会进行第一次
- 单层递归的逻辑：向左遍历，如果左孩子不为空就先给depth++，然后递归函数(root.left,depth)，然后回溯，回溯要给depth--。这里为什么要--，因为处理完左孩子回溯后就要到右孩子了对吧，遍历右孩子时depth又++了，而右节点的深度和左节点是一样的，所以要--。不懂可以看视频的10分钟开始。
- 遍历完左侧又到向右遍历，如果右孩子不为空就如同上面向左遍历的操作
1.2 代码
// 递归法 class Solution { private int Deep = -1; private int value = 0; public int findBottomLeftValue(TreeNode root) { value = root.val; findLeftValue(root,0); return value; } private void findLeftValue (TreeNode root,int deep) { if (root == null) return; if (root.left == null && root.right == null) { if (deep > Deep) { value = root.val; Deep = deep; } } if (root.left != null) findLeftValue(root.left,deep + 1); if (root.right != null) findLeftValue(root.right,deep + 1); } }
2. LeetCode 112. 路径总和113. 路径总和 II
2.1 思路
- 本题依然是前中后序都可以，因为不涉及根节点的处理
- 递归函数的参数和返回值：为什么需要boolean返回值？因为这题是要找到一条符合的路径即可，没必要遍历全部的节点，因此需要返回值，并且是boolean；参数是TreeNode，计数器count，这个count的用法是目标值-节点的值，遇到一个减一个，如果到叶子节点的时候count==0，那就说明路径符合
- 终止条件：遇到叶子节点就要判断了，if(node.left==null&&node.right==null&&count==0)就说明叶子节点的时候count为0，就是路径了，true。if(node.left==null&&node.right==null&&count!=0)就说明不是对应路径
- 单层递归逻辑：向左遍历，如果左孩子不为空就先，count减去左孩子的值，然后向左递归传入（左孩子，count），因为这个函数返回的是布尔值，如果判断是返回true，那就说明已经找到路径了，那就return true，如果判断是返回false，那就回溯，count加上原来左孩子的值，为什么要加回来？因为返回false说明这条路径不对，要向右递归的时候值应该是原来的值。这部分不懂可以从视频的11分钟开始看。
- 向右遍历同上面向左遍历的逻辑
2.2 代码
//112. 路径总和 class Solution { private boolean traversal(TreeNode cur, int count) { if (cur.left == null && cur.right == null && count == 0) return true; // 遇到叶子节点，并且计数为0 if (cur.left == null && cur.right == null) return false; // 遇到叶子节点直接返回 if (cur.left != null) { // 左 count -= cur.left.val; // 递归，处理节点; if (traversal(cur.left, count)) return true; count += cur.left.val; // 回溯，撤销处理结果 } if (cur.right != null) { // 右 count -= cur.right.val; // 递归，处理节点; if (traversal(cur.right, count)) return true; count += cur.right.val; // 回溯，撤销处理结果 } return false; } public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; return traversal(root, sum - root.val); } } //113. 路径总和 II class Solution { private List<List<Integer>> result; private List<Integer> path; private void traversal(TreeNode cur, int count) { if (cur.left == null && cur.right == null && count == 0) { // 遇到了叶子节点且找到了和为sum的路径 result.add(new ArrayList<>(path)); return; } if (cur.left == null && cur.right == null) return; // 遇到叶子节点而没有找到合适的边，直接返回 if (cur.left != null) { // 左 （空节点不遍历） path.add(cur.left.val); count -= cur.left.val; traversal(cur.left, count); // 递归 count += cur.left.val; // 回溯 path.remove(path.size() - 1); // 回溯 } if (cur.right != null) { // 右 （空节点不遍历） path.add(cur.right.val); count -= cur.right.val; traversal(cur.right, count); // 递归 count += cur.right.val; // 回溯 path.remove(path.size() - 1); // 回溯 } } public List<List<Integer>> pathSum(TreeNode root, int sum) { result = new ArrayList<>(); path = new ArrayList<>(); if (root == null) return result; path.add(root.val); // 把根节点放进路径 traversal(root, sum - root.val); return result; } }
3. LeetCode 106. 从中序与后序遍历序列构造二叉树105. 从前序与中序遍历序列构造二叉树
3.1 思路
- 我们要确定一个节点的值，这个节点就在于"中"，所以我们要明确遍历的顺序
- 中序是左中右，后序是左右中，这说明后序里的最后一个元素就是中，而这个元素就是二叉树的根节点了，那又看中序遍历里，以这个元素为中，左右的元素就分别说左子树和右子树了，然后再看后序遍历，就可以分出左右子树了，从这里又可以看出左右子树的"中"是那个了，又可以看回中序遍历确定以某个元素为"中"的左右子树了，以此类推
- 递归函数的参数和返回值：返回值是一个节点，参数是两个数组，中序和后序
- 终止条件：后序数组为0就说明已经没有节点了，就return null
- 单层递归的逻辑：找到切割点，nodeVal=postorder[postorder.length-1]；node=new TreeNode(nodeVal);如果（后序数组的长度==）就是只有一个节点，那就是遍历到叶子节点了，就return这个节点就可以了。
- 记录上述返回的切割点，然后遍历中序数组，如果找到了这个切割点就把这个点的下标记录起来，然后就是切中序数组，为了得到一个左中序数组和一个右中序数组
- 然后说切后序数组，拿着左中序数组的大小去切后序数组的左区间，剩下的就是右区间，就得到一个左后序和右后序的数组
- 然后就是递归了，左子树=travel(左中序数组，左后序数组)，右子树=travel(右中序数组，右后序数组)
- 最后就返回root
- 中序和前序构造二叉树同理。但是前序和后序不可以，前序是“中左右”后序是“左右中”，可以知道“中”分别是在第一个和最后一个，关键是“左右”的区间不知道，左区间和右区间的分割点找不到，中序遍历的关键就是可以找到左右区间的间隔
3.2 代码
//106.从中序与后序遍历序列构造二叉树 class Solution { Map<Integer, Integer> map; // 方便根据数值查找位置 public TreeNode buildTree(int[] inorder, int[] postorder) { map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置 map.put(inorder[i], i); } return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开 } public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) { // 参数里的范围都是前闭后开 if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树 return null; } int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数 root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft); root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1); return root; } } //105.从前序与中序遍历序列构造二叉树 class Solution { Map<Integer, Integer> map; public TreeNode buildTree(int[] preorder, int[] inorder) { map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置 map.put(inorder[i], i); } return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); // 前闭后开 } public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) { // 参数里的范围都是前闭后开 if (preBegin >= preEnd || inBegin >= inEnd) { // 不满足左闭右开，说明没有元素，返回空树 return null; } int rootIndex = map.get(preorder[preBegin]); // 找到前序遍历的第一个元素在中序遍历中的位置 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数 root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1, inorder, inBegin, rootIndex); root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd, inorder, rootIndex + 1, inEnd); return root; } }
