树的相关算法

- Definition for a binary tree node.
- public class TreeNode {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) { val = x; }
- }
  */
  class  {
  public boolean isSameTree(TreeNode p, TreeNode q) {
      if(p == null && q == null)
          return true;
      if(p == null || q == null)
          return false;
      if(p.val != q.val)
          return false;
      boolean t1 = isSameTree(p.left, q.left);
      boolean t2 = isSameTree(p.right, q.right);
      if(t1 == false || t2 == false)
          return false;
      return true;
  }
  }

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)
            return true;
        return helper(root.left,root.right);
     
    }
    private boolean helper(TreeNode root1, TreeNode root2){
        if(root1==null)
            return root2==null;
        if(root2==null)
            return root1==null;
        return        root1.val==root2.val&&helper(root1.left,root2.right)&&helper(root1.right,root2.left);
    }
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    public int maxDepth(TreeNode root) {
        if(root == null) {return 0;}
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return res;
        Queue<TreeNode> que = new LinkedList();   
        que.add(root);
        while(!que.isEmpty()){
            int count = que.size();
            List<Integer> list = new ArrayList();
            while(count > 0){
                TreeNode node = que.peek();
                que.poll();
                list.add(node.val);
                if(node.left != null) que.add(node.left);
                if(node.right != null) que.add(node.right);
                count--;
            }
            res.add(list);
        } 
        Collections.reverse(res);
        return res;
    }
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    private TreeNode helper(int[] arr,int lo,int hi) {
		if(lo>hi) {
			return null;
		}
		int mid=(lo+hi)/2;
		TreeNode node=new TreeNode(arr[mid]);
		
		node.left=helper(arr, lo, mid-1);
		node.right=helper(arr, mid+1, hi);
	    return node;
	}
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
     
        int lhigh = helper(root.left);
        int rhigh = helper(root.right);
   
        return Math.abs(lhigh - rhigh) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int helper(TreeNode node){    
        if(node == null)return 0;
        return Math.max(helper(node.left), helper(node.right)) + 1;
    }
}

 * 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 minDepth(TreeNode root) {
        if(root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
    }
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
       if(root == null) return false;
       if(root.left == null && root.right == null && sum - root.val == 0) return true;
       return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        TreeNode temp = left;
        root.left = right;
        root.right = temp;
        return root;
    }
}

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) return root;
        else if(left != null) return left;
        else if(right != null) return right;
        else return null;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList();
        if(root != null) helper(root, "" , res);
        return res;
    }
    private void helper(TreeNode root,String path, List<String> res){
        if(root.left == null && root.right == null) res.add(path + root.val);
        if(root.left != null) helper(root.left, path + root. val + "->" , res);
        if(root.right != null) helper(root.right, path + root. val  +"->", res);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// class Solution {
//     public int sumOfLeftLeaves(TreeNode root) {
//         int[] sum = new int[1];	//定义
//         sum[0] = 0;
//         if(root == null) return 0;
//         if(root.left == null && root.right == null) return 0;
//         if(root != null){ 
//              helper(3, root, sum);
//         }
//         return sum[0];
//     }
//     private void helper(int from, TreeNode node, int[] sum){
//         if(node.left == null && node.right == null && from == 1) {
//             sum[0] = sum[0] + node.val;
//         }
//         if(node.left != null)  helper(1, node.left, sum);
//         if(node.right != null)   helper(0, node.right, sum);

//     }
// }
public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int sum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        } else {
            sum += sumOfLeftLeaves(root.left);
        }
        sum += sumOfLeftLeaves(root.right);
        return sum;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null)return 0;
        Queue<TreeNode> que = new LinkedList();
        int res = 0;
        que.offer(root);
        while(! que.isEmpty()){
            TreeNode node = que.poll();
            int tnum = helper(node, sum);
            res += tnum;
            if(node.left != null) que.offer(node.left);
            if(node.right != null) que.offer(node.right);
    
        }
        return res;
    }
    private int helper(TreeNode node, int sum){
       if(node == null) return 0;
       if(sum - node.val == 0) return helper(node.left, sum - node.val) + helper(node.right, sum - node.val) + 1; 
       else return helper(node.left, sum - node.val) + helper(node.right, sum - node.val);
    }
}

=============
public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int pathSumFrom(TreeNode node, int sum) {
        if (node == null) return 0;
        return (node.val == sum ? 1 : 0) 
            + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
    }
}

#复杂度有点高 todo
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer,Integer> map = new HashMap();
    int max;
    public int[] findMode(TreeNode root) {
        if(root==null) return new int[0]; 
        helper(root);
        List<Integer> list = new ArrayList();
        for(int key: map.keySet()){
            if(map.get(key) == max) list.add(key);
        }
        int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
        return res;
     
    }
    
    private void helper(TreeNode node){
        if(node.left != null) helper(node.left);
        map.put(node.val, map.getOrDefault(node.val, 0)+1);
        max = Math.max(max, map.get(node.val));
        if(node.right != null) helper(node.right);
    }
}

#todo
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    public boolean helper(TreeNode root, int minVal, int maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return helper(root.left, minVal, root.val) & helper(root.right, root.val, maxVal);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min = Integer.MAX_VALUE;
    Integer prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        
        getMinimumDifference(root.left);
        
        if (prev != null) {
            min = Math.min(min, root.val - prev);
        }
        prev = root.val;
        
        getMinimumDifference(root.right);
        
        return min;
    }
    
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int prev = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        convertBST(root.right);
        root.val = root.val + prev;
        prev = root.val;
        convertBST(root.left);
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxDim = Integer.MIN_VALUE;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        helper(root);
        return maxDim;        
    }
    private int helper(TreeNode node){
        if(node == null)return 0;
        int left = helper(node.left);
        int right = helper(node.right);
        maxDim = Math.max(maxDim, left + right);
        return Math.max(left, right) + 1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (helper(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    private boolean helper(TreeNode s, TreeNode t){
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val & helper(s.left, t.left) & helper(s.right, t.right);
    }
}

/**todo
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode tree;
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null)return t2;
        if(t2 != null){
            t1.val += t2.val;
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
        }
        return t1;
    }
}