重生之我在代码随想录刷算法第十四天 | 513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树
参考文献链接：代码随想录
本人代码是Java版本的，如有别的版本需要请上代码随想录网站查看。
513.找树左下角的值
[力扣题目链接]
解题思路
该题目的意思就是找最深层的最左边的元素，所以其实我们用什么顺序遍历都行，因为没有中的处理逻辑，只需要左比右更靠前就行。
或者可以用迭代法层序遍历，这个方法十分简单。
递归法
首先有result保存结果，maxDepth保存的是当前最大的深度，当有更深的就替换，这样可以确保找到的是深度最大的。
class Solution {int result = 0;int maxDepth = Integer.MIN_VALUE;public int findBottomLeftValue(TreeNode root) {digui(root,0);return result;}//遍历传入当前元素和当前深度public void digui(TreeNode node,int depth){if(node.left == null && node.right == null){//终止条件是叶子节点，然后就判断深度是否最深if(depth > maxDepth){maxDepth = depth;result = node.val;}}//先左后右，当左边被保存为result时，深度也更新了，那么右边即使遍历也不会保存，因为深度不够。if(node.left != null){digui(node.left,depth + 1);}if(node.right != null){digui(node.right,depth + 1);}}
}
迭代法层序遍历
层序遍历一层比一层深，所以我们只需要每次保存每一层的最左边节点即可，最后留下的就是最深最左的。
class Solution {public int findBottomLeftValue(TreeNode root) {int result = root.val;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int len = queue.size();int count = len;while(len-- > 0){TreeNode temp = queue.poll();if(count - 1 == len){result = temp.val; }if(temp.left != null){queue.offer(temp.left);}if(temp.right != null){queue.offer(temp.right);}}}return result;}
}
112. 路径总和
112.路径总和
113.路径总和ii
解题思路
这两道题比较类似，就是递归求路径总和，但还要加上回溯这样才能把每种情况都找到，不然只递归的话就只有一条路径了
注意点
res.add(new LinkedList<>(path));
该代码中res是路径总和ii中保存总结果的List<List>
path是List
在添加时为什么要这样呢，如果直接res.add(path); 当path改变结果就会改变，对于我们这道题，path会进行回溯，我们为了保存到完整的结果，所以new LinkedList去保存它。
112.路径总和
class Solution {boolean flag = false;public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null){return false;}path(root,0,targetSum);return flag;}public void path(TreeNode node,int pathSum,int targetSum){if(node.left == null && node.right == null){if(pathSum + node.val == targetSum){flag = true;}}if(node.left != null){path(node.left,pathSum + node.val,targetSum);}if(node.right != null){path(node.right,pathSum + node.val,targetSum);}}
}
113.路径总和ii
class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new LinkedList<>();if (root == null) return res; // 非空判断List<Integer> path = new LinkedList<>();preorderdfs(root, targetSum, res, path);return res;}public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {path.add(root.val);// 遇到了叶子节点if (root.left == null && root.right == null) {// 找到了和为 targetsum 的路径if (targetsum - root.val == 0) {res.add(new LinkedList<>(path));}return; // 如果和不为 targetsum，返回}if (root.left != null) {preorderdfs(root.left, targetsum - root.val, res, path);path.remove(path.size() - 1); // 回溯}if (root.right != null) {preorderdfs(root.right, targetsum - root.val, res, path);path.remove(path.size() - 1); // 回溯}}
}
106.从中序与后序遍历序列构造二叉树
力扣题目链接
解题思路
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3]
首先我们要知道根节点，后序遍历的最后一个节点就一定是根节点。是3
然后去中序遍历3可以分割数组为9和15 20 7。 9就是左，15 20 7就是右子树。
然后再去后序遍历，15 7 20，所以20是右子树的根节点。
综上，我们只需要递归一直分割两个数组即可。
代码示例
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length == 0 || postorder.length == 0){return null;}//从后序数组最后一位获取根节点int post = postorder[postorder.length - 1];TreeNode root = new TreeNode(post);int index = 0;//切分中序for(int i = 0;i < inorder.length;i++){if(post == inorder[i]){index = i;break;}}int[] inleft;if(index == 0){inleft = new int[0];}else{inleft = Arrays.copyOfRange(inorder,0,index);}int [] inright = Arrays.copyOfRange(inorder,index+1,inorder.length);//切分后序int[] postleft;int[] postright;if(index == 0){postleft = new int[0];postright = Arrays.copyOfRange(postorder,index,postorder.length-1);}else if(index == inorder.length - 1){postleft = Arrays.copyOfRange(postorder,0,inleft.length);postright = new int[0];}else{postleft = Arrays.copyOfRange(postorder,0,inleft.length);postright = Arrays.copyOfRange(postorder,inleft.length,postorder.length-1);}//继续递归左子树和右子树root.left = buildTree(inleft,postleft);root.right = buildTree(inright,postright);return root;}
}