binary tree

发表于 | 阅读次数:
字数统计: 1,431 | 阅读时长 ≈ 8

本文总结了关于二叉树的相关题目。

先序遍历:

  1. Divide & Conquer 
1
2
3
4
5
6
7
8
9
10
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        result.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        List<Integer> right = preorderTraversal(root.right);
        result.addAll(left);
        result.addAll(right);
        return result;
    }
  1. Traverse 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        traverse(root, result);
        return result;
    }
private void traverse(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        traverse(root.left, result);
        traverse(root.right, result);
    }

比较分治法和遍历的区别：

遍历是没有返回值的，使用一个全局变量去记录数据。一个人拿本子去走

而分治法是有返回值的，分左右治之，再把左右值加进去。一个人去布置任务。

Maximum Depth of Binary Tree **

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example

Given a binary tree as follow:

1
2
3
4
5
  1
 / \ 
2   3
   / \
  4   5
  1. Divide & Conquer
1
2
3
4
5
6
public int maxDepth(TreeNode root) {
   if(root == null) return 0;
   int left = maxDepth(root.left) + 1;
   int right = maxDepth(root.right) + 1;
   return Math.max(left,right);
}
  1. Traverse
1
2
3
4
5
6
7
8
9
10
11
12
private int max;  
public int maxDepth(TreeNode root) {
   max = 0;
   helper(root,0);
   return max;
}
public void helper(TreeNode root, int result){
    if(root == null) return ;
    max = Math.max(max,++result);
    helper(root.left,result);
    helper(root.right,result);
}

Binary Tree Paths **

Given a binary tree, return all root-to-leaf paths.

Example

Given the following binary tree: 

1
2
3
4
5
   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

1
2
3
4
[
  "1->2->5",
  "1->3"
]
  1. Divide & Conquer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<String> binaryTreePaths(TreeNode root) {   
   	List<String> my_result = new LinkedList<>();
    if(root == null) return my_result;
    
    List<String> left = binaryTreePaths(root.left);
    List<String> right = binaryTreePaths(root.right);
    for(String path : left){
        my_result.add(root.val + "->" + path);
    }
    for(String path : right){
        my_result.add(root.val + "->" + path);
    }
    if(my_result.size() == 0)//叶子节点
        my_result.add(root.val+"");
    return my_result;
}
  1. Traverse 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private List<String> result;
    public List<String> binaryTreePaths(TreeNode root) {
        result = new LinkedList();
        if (root == null) {
            return result;
        }
        helper(root,String.valueOf(root.val));
        return result;
    }
    private void helper(TreeNode root,String path){
        if(root == null) return;
        if(root.left == null && root.right == null) {
            result.add(path);
        }//叶子节点
        if(root.left != null)
            helper(root.left, path + "->" + String.valueOf(root.left.val));
        if(root.right != null)
            helper(root.right, path + "->" + String.valueOf(root.right.val));
    }

Minimum Subtree **:

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

Example

Given a binary tree: 

1
2
3
4
5
     1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int min = Integer.MAX_VALUE;
    private TreeNode result = null;
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        helper(root);
        return result;
    }
    public int helper(TreeNode root){
        if(root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        int sum = left + right +root.val;
        if(min > sum){
            min = sum;
            result = root;
        }
        return sum;
    }

pure d-c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class ResultType {
    public TreeNode minSubtree;
    public int sum, minSum;
    public ResultType(TreeNode minSubtree, int minSum, int sum) {
        this.minSubtree = minSubtree;
        this.minSum = minSum;
        this.sum = sum;
    }
}
public TreeNode findSubtree(TreeNode root) {
        ResultType result = helper(root);
        return result.minSubtree;
    }
    
    public ResultType helper(TreeNode node) {
        if (node == null) {
            return new ResultType(null, Integer.MAX_VALUE, 0);
        }
        
        ResultType leftResult = helper(node.left);
        ResultType rightResult = helper(node.right);
        
        ResultType result = new ResultType(
            node,
            leftResult.sum + rightResult.sum + node.val,
            leftResult.sum + rightResult.sum + node.val
        );
        
        if (leftResult.minSum <= result.minSum) {
            result.minSum = leftResult.minSum;
            result.minSubtree = leftResult.minSubtree;
        }
        
        if (rightResult.minSum <= result.minSum) {
            result.minSum = rightResult.minSum;
            result.minSubtree = rightResult.minSubtree;
        }
        
        return result;
    }

Balanced Binary Tree **

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Given binary tree A = {3,9,20,#,#,15,7}, B = {3,#,20,15,7} 

1
2
3
4
5
A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

The binary tree A is a height-balanced binary tree, but B is not. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private boolean isb;
    public boolean isBalanced(TreeNode root) {
        // write your code here
        isb = true;
        helper(root);
        return isb;
    }
    public int helper(TreeNode root){
        //return height
        
        if(root == null || isb == false)return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        if(Math.abs(left - right) > 1)
            isb = false;
        return Math.max(left,right) + 1;
    }

Subtree with Maximum Average **

Given a binary tree, find the subtree with maximum average. Return the root of the subtree.

Example :

Given a binary tree: 

1
2
3
4
5
     1
   /   \
 -5     11
 / \   /  \
1   2 4    -2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private class resultType{
        TreeNode node;
        int sum,num;
        public resultType(TreeNode node, int sum, int num){
            this.node = node;
            this.sum = sum;
            this.num = num;
        }
    }
    private resultType maxNode;
    public TreeNode findSubtree2(TreeNode root) {
        // write your code here
        maxNode = new resultType(null,Integer.MIN_VALUE,1);
        helper(root);
        return maxNode.node;
    }
    public resultType helper(TreeNode root){
        if(root == null) return new resultType(null,0,0);
        resultType left = helper(root.left);
        resultType right = helper(root.right);
        resultType my_result = new resultType(
            root, 
            root.val + left.sum + right.sum, 
            left.num + right.num + 1);//本题与左右的avg无关.
        if(my_result.sum * maxNode.num > maxNode.sum * my_result.num )//key point calculate avg;
            maxNode = my_result;
        return my_result;
    }

Lowest Common Ancestor **

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

For the following binary tree:

1
2
3
4
5
  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

1
2
3
4
5
6
7
8
9
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if(root == null || A == root || B == root)return root;
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if(left != null && right != null) return root;
        if(left != null) return left;
        else return right;
    }

如果root就是A或者B,那么下面就不用遍历了，因为如果另一个在root的左右子树，那么最低的肯定是root

如果root不是A或者B,那么要考察左右子树，如果左右子树都不空，则root就是最低的。

如果左空右不空，那么右边有A或者B的或者两个都有。

如果右空左不空，那么左边是有A或者B或者两个都有。

如果两个都空，那么这颗树没有A或者B.则返回不了咯。