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; } }