#TREE#(╯‵□′)╯︵┻━┻

Leave a comment

October 5, 2016 by oneOokay

  • Maximum Depth of Binary Tree
  • Balanced Binary Tree
  • Minimum Depth of Binary Tree
  • Complete Binary Tree

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.


有三种方法:

Recursive:很简单,引用自身

Queue的BFS:也挺简单,也就是求层数

Stack的可以看一下: 用两个Stack,一个存node,一个存对应node的depth,另一个全局的maxDepth. 不需要考虑pre-order或者in-order的顺序,只要按左右顺序就可以了.

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left); //会一直走到最左叶子节点返回。
        int right = maxDepth(root.right); //会一直走到最右叶子节点返回。
        return Math.max(left, right) + 1; //叶子节点的depth为1
    }

public int maxDepth(TreeNode root) {
 if (root == null) return 0;
 Stack<TreeNode> nodes = new Stack<>();
 Stack<Integer> values = new Stack<>();
 int maxDepth = 0;
 nodes.push(root);
 values.push(1);
 while (!nodes.isEmpty()){
 TreeNode node = nodes.pop();
 int cur = values.pop();
 maxDepth = Math.max(cur, maxDepth);
 if (node.left != null){
 nodes.push(node.left);
 values.push(cur + 1);
 }
 if (node.right != null){
 nodes.push(node.right);
 values.push(cur + 1);
 }
 }
 return maxDepth;
 }

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.


又重新去理解了一下Maximum Depth of Binary Tree,可以用这个。

如果只要某一个node的left和right maxDepth值相差大于1,那么说明这个树就不是balanced binary tree了。于是用-1来mark。

    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) != -1;
    }
    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if (left == -1 || right == -1 || (Math.abs(left-right) > 1)){
            return -1; 
        }
        return Math.max(left, right) + 1;
    }

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.


与max depth有轻微的不同: 当node的一个儿子为null的时候(该儿子的minDepth返回值为0),那么在计算这个node的最小depth的时候,并不能够直接取min(left, right)。这样会永远取到0。所以这时候应该找非null的儿子depth + 1.

public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0 && right != 0) {
return right + 1;
}
if (right == 0 && left != 0) {
return left + 1;
}
return Math.min(left, right) + 1;
}

Complete Binary Tree

Check a binary tree is completed or not. A complete binary tree is a binary tree that every level is completed filled except the deepest level. In the deepest level, all nodes must be as left as possible.

分成左右儿子来看,可能的情况是:它的左儿子和右儿子depth相等或者相差1.

  • 若左儿子和右儿子depth相等那么意味着:左儿子必然是一个满的Tree,每一个儿子节点上都有儿子。右儿子必须为一个complete binary tree才能使得node为complete。
  • 若左儿子和右儿子depth 相差一那么意味着:右儿子必然是一个满的Tree,左儿子必须是一个complete tree才能使得node为complete。

用分治和迭代是肯定的了,可以看到迭代的需要的属性有三个:该node的depth,该node为root的树是否是一个Full tree(所有的儿子节点都是满的),该node为root的树是否是一个Complete tree(不一定所有的儿子节点都是满的但是是complete的)。于是构造出一个ResultType来用来迭代。

class ResultType {
    public int depth;
    public boolean isFull, isComplete;
    ResultType(int depth, boolean isFull, boolean isComplete) {
        this.depth = depth;
        this.isFull = isFull;
        this.isComplete = isComplete;
    }
}

public class Solution {
    /**
     * @param root, the root of binary tree.
     * @return true if it is a complete binary tree, or false.
     */
    public boolean isComplete(TreeNode root) {
        ResultType result = helper(root);
        return result.isComplete;
    }
    
    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, true, true);
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        if (!left.isComplete) { //首先进行左子树判断,如果左子树不是Complete,直接返回
            return new ResultType(-1, false, false);
        }
        // 左右子树depth相等
        if (left.depth == right.depth) {
            if (!left.isFull || !right.isComplete) {//左子树必须为full,右子树必须为complete
                return new ResultType(-1, false, false);
            }
            //该点是否为full取决它的右子树,左子树肯定是full的。而且到这步该点一定为complete
            return new ResultType(left.depth + 1, right.isFull, true);
        }
        
        //左子树depth为右子树depth + 1
        if (left.depth == right.depth + 1) {
            if (!left.isComplete || !right.isFull) {//左子树必须为complete,右子树必须为full
                return new ResultType(-1, false, false);
            }
            //该点由于左右子树depth不等,所以一定不是full。到这步该店一定为complete
            return new ResultType(left.depth + 1, false, true);
        }
        
        return new ResultType(-1, false, false);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: