代码随想录day16| 513找树左下角的值 、 路径总和 、 从中序与后序遍历序列构造二叉树

513找树左下角的值

层序遍历法

使用层序遍历，找到最后一层最左边的数值（每层循环的第一个值）返回即可

class Solution {public int findBottomLeftValue(TreeNode root) {int res = 0;Queue<TreeNode> queue = new LinkedList();queue.offer(root);while(!queue.isEmpty()){int size = queue.size();for(int i = 0 ; i < size ; i++){TreeNode node = queue.poll();if(i == 0){res = node.val;}if(node.left!= null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}} return res;}}

递归法

使用递归遍历二叉树并且记录当前深度，到根节点时更新最大深度的值，然后使用回溯来更新其他路径时的深度

class Solution {int maxDeepth = -1;int res = 0;public int findBottomLeftValue(TreeNode root) {int deepth = 0;getdeepthleft(root, deepth);return res;}public void getdeepthleft(TreeNode root, int deepth){if(root.left == null && root.right == null){if(deepth > maxDeepth){maxDeepth = deepth;res = root.val;return ;}return ;}if(root.left != null){deepth += 1;getdeepthleft(root.left, deepth);deepth -= 1;}if(root.right != null){deepth += 1;getdeepthleft(root.right, deepth);deepth -= 1;}}
}

路径总和

112. 路径总和

使用递归加回溯找出是否有符合目标的路径

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null){return false;}int sum = 0;return getPath(root, sum, targetSum);}public boolean getPath(TreeNode root, int sum, int targetSum){if(root.left == null && root.right == null){if(targetSum == sum + root.val){return true;}return false;}sum += root.val;boolean left = false;boolean right = false;if(root.left != null){left = getPath(root.left, sum, targetSum);}if(root.right != null){right = getPath(root.right, sum, targetSum);}if(left || right){return true; }else{sum -= root.val;return false;}}
}

113. 路径总和 II

这里相比上一个题目需要收集具体的符合目标的路径，所以回溯两个值：当前路径值的和（sum ）、当前收集的路径节点（path ）

class Solution {List<Integer> path = new ArrayList();List<List<Integer>> paths = new ArrayList();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root == null){return paths;}int sum = 0;getPath(root, sum, targetSum);return paths;}public void getPath(TreeNode root, int sum, int targetSum){path.add(root.val);sum += root.val;if(root.left == null && root.right == null){if(targetSum == sum){//这里注意新创建一个列表，不能直接存原列表，因为原列表后序会修改paths.add(new ArrayList(path));}return ;}if(root.left != null){getPath(root.left, sum, targetSum);path.remove(path.size()-1);}if(root.right != null){getPath(root.right, sum, targetSum);path.remove(path.size()-1);}}}

从中序与后序遍历序列构造二叉树

思路

具体思路

注意：切割数组时的边界处理

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return getTree(inorder, postorder);}public TreeNode getTree(int[] inorder, int[] postorder) {if(inorder == null || postorder == null){return null;}int val = postorder[postorder.length-1];TreeNode root = new TreeNode(val);if(inorder.length == 1){return root;}int i = 0;for(;i < inorder.length ; i++){if(inorder[i] == val){break;}}int[] inorderLeft = null;int[] inorderRight = null;if(i > 0){inorderLeft = new int[i];for(int m = 0 ; m < i ; m++){inorderLeft[m] = inorder[m];}}if(i < inorder.length-1){inorderRight = new int[inorder.length-i-1];int n = 0;for(int m = i+1 ; m < inorder.length ; m++){inorderRight[n++] = inorder[m];}}int j = 0;int[] postorderLeft = null;int[] postorderRight = null;if(inorderLeft != null){postorderLeft = new int[inorderLeft.length];for(int m = 0 ; m < inorderLeft.length ; m++){postorderLeft[m] = postorder[m];}}if(inorderRight!=null){postorderRight = new int[inorderRight.length];int n = 0;int m = 0;if(inorderLeft != null){m = inorderLeft.length;}for(; m < postorder.length-1 ; m++){postorderRight[n] = postorder[m];System.out.print(postorderRight[n] + " ");n++;}}root.left = getTree(inorderLeft, postorderLeft);root.right = getTree(inorderRight, postorderRight);return root;}}