代码随想录算法训练营Day14

513.找树左下角的值

力扣题目链接：. - 力扣（LeetCode）

层序遍历

class Solution {public int findBottomLeftValue(TreeNode root) {if(root==null){return 0;}Deque<TreeNode> myque=new LinkedList<>();myque.offer(root);int count=0;while(!myque.isEmpty()){count++;int len=myque.size();while(len>0){TreeNode cur=myque.poll();if(cur.left!=null){myque.offer(cur.left);}if(cur.right!=null){myque.offer(cur.right);}len--;}}int count1=1;myque.offer(root);while(count1<count){count1++;int len=myque.size();while(len>0){TreeNode cur=myque.poll();if(cur.left!=null){myque.offer(cur.left);}if(cur.right!=null){myque.offer(cur.right);}len--;}}TreeNode cur2=myque.poll();return cur2.val;}
}

112. 路径总和

力扣题目链接：. - 力扣（LeetCode）

前序递归

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null){return false;}List<Integer> path=new ArrayList<>();     return hasSum(root,path,targetSum);}public boolean hasSum(TreeNode root,List<Integer> path,int targetSum){path.add(root.val);if(root.left==null&&root.right==null){int sum=0;for(Integer i:path){sum+=i;}if(sum==targetSum)return true;return false;}if(root.left!=null){boolean has=hasSum(root.left,path,targetSum);if(has)return has;path.remove(path.size()-1);}if(root.right!=null){boolean has=hasSum(root.right,path,targetSum);if(has)return has;path.remove(path.size()-1);}return false;}}

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

力扣题目链接. - 力扣（LeetCode）

循环不变量，前序递归

class Solution {Map<Integer,Integer> inordermap;public TreeNode buildTree(int[] inorder, int[] postorder) {inordermap=new HashMap<>();for(int i=0;i<inorder.length;i++){inordermap.put(inorder[i],i);}return fondNode(inorder,0,inorder.length,postorder,0,postorder.length);}public TreeNode fondNode(int[] inorder,int instart,int inend,int[]postorder,int poststart,int postend){if(instart>=inend||poststart>=postend){return null;}int inindex=inordermap.get(postorder[postend-1]);TreeNode root=new TreeNode(postorder[postend-1]);int leftLen=inindex-instart;root.left=fondNode(inorder,instart,inindex,postorder,poststart,poststart+leftLen);root.right=fondNode(inorder,inindex+1,inend,postorder,poststart+leftLen,postend-1);return root;}
}