阅读量:0
算法笔记|Day14二叉树IV
- ☆☆☆☆☆leetcode 513.找树左下角的值
- ☆☆☆☆☆leetcode 112. 路径总和
- ☆☆☆☆☆leetcode 113.路径总和II
- ☆☆☆☆☆leetcode 106.从中序与后序遍历序列构造二叉树
- ☆☆☆☆☆leetcode 105.从前序与中序遍历序列构造二叉树
☆☆☆☆☆leetcode 513.找树左下角的值
题目链接：leetcode 513.找树左下角的值
题目分析
本题递归+回溯，采用前序、中序、后序遍历均可，只需先处理左节点再处理右节点均可，不涉及中节点的处理逻辑；另外可以采用迭代层序遍历更简单。
代码
1.1递归 class Solution { int maxDepth=Integer.MIN_VALUE; int result; public int findBottomLeftValue(TreeNode root) { result=root.val; traversal(root,0); return result; } public void traversal(TreeNode root,int depth){ if(root==null) return; if(root.left==null&&root.right==null){ if(depth>maxDepth){ maxDepth=depth; result=root.val; } } if(root.left!=null){ depth++; traversal(root.left,depth); depth--; } if(root.right!=null){ depth++; traversal(root.right,depth); depth--; } } } 1.2递归（精简版本） class Solution { int maxDepth=Integer.MIN_VALUE; int result; public int findBottomLeftValue(TreeNode root) { result=root.val; traversal(root,0); return result; } public void traversal(TreeNode root,int depth){ if(root==null) return; if(root.left==null&&root.right==null){ if(depth>maxDepth){ maxDepth=depth; result=root.val; } } if(root.left!=null) traversal(root.left,depth+1); if(root.right!=null) traversal(root.right,depth+1); } } 2.迭代，层序遍历 class Solution { public int findBottomLeftValue(TreeNode root) { Deque<TreeNode> deque=new LinkedList<>(); deque.add(root); int res=0; while(!deque.isEmpty()){ int size=deque.size(); for(int i=0;i<size;i++){ TreeNode temp=deque.poll(); if(i==0) res=temp.val; if(temp.left!=null) deque.add(temp.left); if(temp.right!=null) deque.add(temp.right); } } return res; } } ☆☆☆☆☆leetcode 112. 路径总和
题目链接：leetcode 112. 路径总和
题目分析
本题递归+回溯，采用前序、中序、后序遍历均可，不涉及中节点的处理逻辑。
代码
1.1递归+回溯 class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; return traversal(root,targetSum-root.val); } public boolean traversal(TreeNode node,int count){ if(node==null) return false; if(node.left==null&&node.right==null&&count==0) return true; if(node.left==null&&node.right==null&&count!=0) return false; if(node.left!=null){ count-=node.left.val; if(traversal(node.left,count))return true; count+=node.left.val; } if(node.right!=null){ count-=node.right.val; if(traversal(node.right,count))return true; count+=node.right.val; } return false; } } 1.2递归+回溯（精简版本） class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; targetSum-=root.val; if(root.left==null&&root.right==null) return targetSum==0; if(root.left!=null) if(hasPathSum(root.left,targetSum)) return true; if(root.right!=null) if(hasPathSum(root.right,targetSum)) return true; return false; } } 1.3递归+回溯（更精简版本） class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; if(root.left==null&&root.right==null&&targetSum==root.val) return true; return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val); } } ☆☆☆☆☆leetcode 113.路径总和II
题目链接：leetcode 113.路径总和II
题目分析
递归+回溯，采用前序、中序、后序遍历均可，不涉及中节点的处理逻辑，要遍历所有路径所以递归函数不需要返回值。
代码
class Solution { List<List<Integer>> result; List<Integer> path; public List<List<Integer>> pathSum(TreeNode root, int targetSum) { result=new LinkedList<>(); path=new LinkedList<>(); traversal (root,targetSum); return result; } public void traversal(TreeNode root,int count){ if(root==null) return; path.add(root.val); if(root.left==null&&root.right==null&&count==root.val) result.add(new LinkedList<>(path)); traversal(root.left,count-root.val); traversal(root.right,count-root.val); path.removeLast(); } } ☆☆☆☆☆leetcode 106.从中序与后序遍历序列构造二叉树
题目链接：leetcode 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 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]); root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+(rootIndex-inBegin)); root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+(rootIndex-inBegin),postEnd-1); return root; } } 提示：inBegin >= inEnd || postBegin >= postEnd不满足左闭右开，说明没有元素，返回空树
☆☆☆☆☆leetcode 105.从前序与中序遍历序列构造二叉树
题目链接：leetcode 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.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]); root.left=findNode(preorder,preBegin+1,preBegin+(rootIndex-inBegin)+1,inorder,inBegin,rootIndex); root.right=findNode(preorder,preBegin+(rootIndex-inBegin)+1,preEnd,inorder,rootIndex+1,inEnd); return root; } } 提示：preBegin>=preEnd||inBegin>=inEnd不满足左闭右开，说明没有元素，返回空树
