【算法第十五天7.29】513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树

链接力扣513-找树左下角的值

思路

class Solution {public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = 0;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;}
}

链接力扣112-路径总和

思路

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// 用前序遍历if(root == null) return false;if(root.left == null && root.right == null) return targetSum == root.val;// 求两侧分支的路径和return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}
}

链接力扣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.put(inorder[i],i);}return 	getRoot(inorder,0,inorder.length,postorder,0,postorder.length);}public TreeNode getRoot(int[] inorder, int inStart,int inEnd,int[] postorder,int postStart,int postEnd){// 参数里的范围都是前闭后开,不是左闭右开，则无法返回树if(inStart >= inEnd || postStart >= postEnd) return null;// 获取中序中的根节点值；int index = map.get(postorder[postEnd - 1]);TreeNode root = new TreeNode(inorder[index]);// 求出左树的长度int lenOfLeft = index - inStart;// 根据左闭右开，来建立左子树、右子树root.left = getRoot(inorder,inStart,index, postorder,postStart,postStart + lenOfLeft);root.right = getRoot(inorder,index + 1, inEnd, postorder,postStart + lenOfLeft,postEnd - 1);// root.right = getRoot(inorder,index + 1, inEnd, postorder,postStart + index,postEnd - 1);return root;}
}