97.Maximam Depth of Binary Tree： 点击打开链接
/* Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ public int maxDepth(TreeNode root) { if(root==null){ //出口：就是一眼就能看出结果的 return 0; } int leftDepth=maxDepth(root.left); //先无脑地得到左子树的高度 int rightDepth=maxDepth(root.right); //再无脑地得到右子树的高度 return Math.max(leftDepth,rightDepth)+1; } }155.Minimum Depth of Binary Tree：点击打开链接
思路：计算左子树和右子树深度的时候，要先判断是否等于0，如果等于0，就说明这边的子树不存在，可以认为这边子树的深度为无限大，
因此整个树的最小深度要看另一边有子树的深度
注意：出现斜树的情况，就是说只有左子树或者只有右子树的时候，这时候明显没有子树的这一边深度为0，但是不能说此时树的最小深度为0
这种情况下，就按有子树的那边的最小深度来计
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ public int minDepth(TreeNode root) { if(root==null){ return 0; } int leftDepth=minDepth(root.left); int rightDepth=minDepth(root.right); return (leftDepth==0 || rightDepth==0) ? leftDepth+rightDepth+1 : Math.min(leftDepth,rightDepth)+1; } }101. Symmetric Tree (LeetCode)
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3But the following [1,2,2,null,3,null,3] is not:
1 / \ 2 2 \ \ 3 3Note: Bonus points if you could solve it both recursively and iteratively.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) { return true; } return isMirror(root.left, root.right); } //Note: 这是一道由孩子结点，深入判断到孩子的孩子结点层次的题 private boolean isMirror(TreeNode p, TreeNode q) { if(p == null && q == null) { return true; } if(p != null && q !=null) { return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right,q.left); } return false; } }
112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:Given the below binary tree and sum = 22,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root==null){ return false; } if(root.left==null && root.right==null){ if(root.val==sum){ return true; } } return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); } }
113.Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:Given the below binary tree and sum = 22,
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1return
[ [5,4,11,2], [5,8,4,5] ]思路：当根节点下面没有左右节点的时候，判断根节点的值是不是等于给定sum
如果根节点有左右节点的时候，递归判断
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result=new ArrayList<>(); List<Integer> path=new ArrayList<>(); if(root==null){ return result; } helper(root,sum,result,path); return result; } private void helper(TreeNode root, int sum,List<List<Integer>> result,List<Integer> path){ if(root==null){ return; } if(root.left==null && root.right==null){ if(root.val==sum){ path.add(root.val); result.add(path); return; } } if(root.left!=null){ List<Integer> leftPath=new ArrayList<>(path); leftPath.add(root.val); helper(root.left,sum-root.val,result,leftPath); } if(root.right!=null){ List<Integer> rightPath=new ArrayList<>(path); rightPath.add(root.val); helper(root.right,sum-root.val,result,rightPath); } } } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //全局的results更好理解，只要满足条件的list就加进去结果results里面 List<List<Integer>> results = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { List<Integer> list = new ArrayList<>(); if(root == null) { return results; } getPath(list, root, sum); return results; } private void getPath(List<Integer> list, TreeNode root, int sum) { //st<List<Integer>> results = new ArrayList<>(); if(root == null) { return; } if(root.left == null && root.right == null) { if(root.val == sum) { list.add(root.val); results.add(list); return; } } if(root.left != null) { List<Integer> leftList = new ArrayList<>(list); leftList.add(root.val); getPath(leftList, root.left, sum - root.val); } if(root.right != null) { List<Integer> rightList = new ArrayList<>(list); rightList.add(root.val); getPath(rightList, root.right, sum - root.val); } } }437. Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11思路：这题和I,II不同之处在于，符合条件的不仅仅是从root开始，任意node开始的都算数
因此最后的结果分为三部分情况：root开始的+root.left开始的+root.right开始的
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int pathSum(TreeNode root, int sum) { if (root==null) { return 0; } return helper(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum); } //最后是以根节点开始的+以根节点的左孩子开始的+以根节点的右孩子开始的 private int helper(TreeNode root, int sum) { if (root==null){ return 0; } int left=helper(root.left, sum-root.val); int right=helper(root.right, sum -root.val); return (root.val==sum?1:0)+left+right; //以根节点开始的符合要求的串 } } /** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { private int totalNums = 0; public int PathSum(TreeNode root, int sum) { if(root == null) { return 0; } if(root != null) { GetValidNums(root, sum); } if(root.left != null) { totalNums = PathSum(root.left, sum); } if(root.right != null) { totalNums = PathSum(root.right, sum); } return totalNums; } // 某node开始的符合条件的path总数 private void GetValidNums(TreeNode root, int sum) { if(root.val == sum) { totalNums++; } if(root.left != null) { GetValidNums(root.left, sum-root.val); } if(root.right != null) { GetValidNums(root.right, sum-root.val); } } }
480. Binary Tree Paths：点击打开链接
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { //divide & conquer方法 /** * @param root the root of the binary tree * @return all root-to-leaf paths */ //递归的定义:以root出发的从头到尾的路径 public List<String> binaryTreePaths(TreeNode root) { List<String> results=new ArrayList<>(); //递归的出口 if(root==null){ return results; } if(root.left==null && root.right==null){ results.add(root.val+"") ; //注意结果是要字符串，加""使结果转变为字符串 } //递归的拆解 divide & conquer List<String> leftPaths=binaryTreePaths(root.left); //先不管三七二十一得到左子树的所有路径 List<String> rightPaths=binaryTreePaths(root.right); //然后再得到右子树所有路径 //merge for(String path:leftPaths){ results.add(root.val+"->"+path); } for(String path:rightPaths){ results.add(root.val+"->"+path); } return results; } }376. Binary Tree Path Sum
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) { List<List<Integer>> result=new ArrayList<>(); List<Integer> path=new ArrayList<>(); if(root==null){ return result; } path.add(root.val); //先装入root.val再进行helper递归 helper(root,target,root.val,result,path); return result; } private void helper(TreeNode root,int target,int sum,List<List<Integer>> result,List<Integer> path){ if(root.left==null && root.right==null){ if(sum==target){ result.add(new ArrayList<Integer>(path)); } return; } if(root.left!=null){ path.add(root.left.val); helper(root.left,target,sum+root.left.val,result,path); path.remove(path.size()-1); } if(root.right!=null){ path.add(root.right.val); helper(root.right,target,sum+root.right.val,result,path); path.remove(path.size()-1); } } }246.Binary tree Path Sum II
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root the root of binary tree * @param target an integer * @return all valid paths */ public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) { List<List<Integer>> result=new ArrayList<>(); return differentRoot(root,target,result); } public List<List<Integer>> differentRoot(TreeNode root, int target,List<List<Integer>> result){ if(root==null) return result; helper(root,target,result,new ArrayList<>()); if(root.left!=null){ differentRoot(root.left,target,result); } if(root.right!=null){ differentRoot(root.right,target,result); } return result; } //find all result in the path from this root public void helper(TreeNode root, int target,List<List<Integer>> result,List<Integer> list){ if(target==root.val){ List<Integer> temp= new ArrayList<>(list); temp.add(root.val); result.add(temp); } if(root.left!=null){ list.add(root.val); helper(root.left,target-root.val,result,list); list.remove(list.size()-1); } if(root.right!=null){ list.add(root.val); helper(root.right,target-root.val,result,list); list.remove(list.size()-1); } } }596.Binary tree Maximum Path Sum II
思路：根据题目说明，至少会有root是最大值，因此在递归定义：以root为根的路径中和最大者，路径不一定是完整的，随时可以终止
所以要比较root值与以root为根的所有路径的值
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /* * @param root: the root of binary tree. * @return: An integer */ public int maxPathSum2(TreeNode root) { if(root==null){ return 0; } int maxVal=Integer.MIN_VALUE; int sum=Math.max(root.val,(root.val+Math.max(maxPathSum2(root.left),maxPathSum2(root.right)))); if(sum>maxVal){ maxVal=sum; } return maxVal; } }596.Minimum Subtree：点击打开链接
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root the root of binary tree * @return the root of the minimum subtree */ private int subtreeSum=Integer.MAX_VALUE; private TreeNode subtree=null; public TreeNode findSubtree(TreeNode root) { helper(root); return subtree; } private int helper(TreeNode root){ if(root==null){ return 0; } int sum=root.val+helper(root.left)+helper(root.right); //这个这一步就完成了divide & conquer，merge if(sum<subtreeSum){ //然后遍历打擂 subtreeSum=sum; subtree=root; } return sum; } } /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root the root of binary tree * @return the root of the minimum subtree */ private int subtreeSum=Integer.MAX_VALUE; private TreeNode subRoot=null; public TreeNode findSubtree(TreeNode root) { helper(root); return subRoot; } private int helper(TreeNode root){ if(root==null){ return 0; } if(root.left==null && root.right==null){ //这部分可以不写，因为下面的情况已经包含这个case int sum= root.val; if(sum<subtreeSum){ subtreeSum=sum; subRoot=root; } return root.val; } int sum=root.val+helper(root.left)+helper(root.right); if(sum<subtreeSum){ subtreeSum=sum; subRoot=root; } return sum; } }597.Subtree with Maximum Average: 点击打开链接
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root the root of binary tree * @return the root of the maximum average of subtree */ private class ResultType{ //创建内部类封装sum,size int sum,size; public ResultType(int sum,int size){ this.size=size; this.sum=sum; } } private ResultType subtreeResult=null; private TreeNode subtree=null; public TreeNode findSubtree2(TreeNode root) { helper(root); return subtree; } public ResultType helper(TreeNode root){ if(root==null){ return new ResultType(0,0); } ResultType leftResult=helper(root.left); ResultType rightResult=helper(root.right); ResultType result=new ResultType(leftResult.sum+rightResult.sum+root.val, leftResult.size+rightResult.size+1); if(subtree==null || result.sum*subtreeResult.size>subtreeResult.sum*result.size){ subtreeResult=result; //防止除数为0，写成交叉相乘的方法 subtree=root; } return result; } }236. Lowest Common Ancestor of a Binary Tree
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { //no parent pointer /** * @param root: The root of the binary search tree. * @param A and B: two nodes in a Binary. * @return: Return the least common ancestor(LCA) of the two nodes. */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) { if(root==null || root==A || root==B){ return root; } TreeNode left=lowestCommonAncestor(root.left, A, B); TreeNode right=lowestCommonAncestor(root.right, A, B); if(left!=null && right!=null){ //左右都不空，返回它们的root return root; } if(left!=null){ //左不空，也就是左不空，同时右空 return left; } if(right!=null){ //右不空，也就是右不空，同时左空 return right; } //if(left==null && right==null){ // return null; //} return null; } }
474. Lowest Common Ancestor II : 点击打开链接
/** * Definition of ParentTreeNode: * * class ParentTreeNode { * public ParentTreeNode parent, left, right; * } */ public class Solution { //with parent pointer /** * @param root: The root of the tree * @param A, B: Two node in the tree * @return: The lowest common ancestor of A and B */ public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) { ArrayList<ParentTreeNode> pathA=getPaths(A); //拿到两条path ArrayList<ParentTreeNode> pathB=getPaths(B); int indexA=pathA.size()-1; //两个ArrayList里从后往前比较 int indexB=pathB.size()-1; //因为tree装在ArrayList的时候，是先装孩子，再向上遍历拿到父母装父母 ParentTreeNode lowestAncestor=null; while(indexA>=0 && indexB>=0){ if(pathA.get(indexA)!=pathB.get(indexB)){ //只要是两条path拿到的当前值不一样，就停止 break; } lowestAncestor=pathA.get(indexA); //不断打擂找lowestAncestor indexA--; indexB--; } return lowestAncestor; } private ArrayList<ParentTreeNode> getPaths(ParentTreeNode node){ ArrayList<ParentTreeNode> result=new ArrayList<>(); while(node!=null){ result.add(node); node=node.parent; } return result; } }
