Leetcode - Count Complete Tree Nodes

Paste_Image.png

My code:

/**
 * 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 countNodes(TreeNode root) {
        if (root == null)
            return 0;
        int left = 1 + getLeftHeight(root);
        int right = 1 + getRightHeight(root);
        if (left == right)
            return (1 << left) - 1;
        else
            return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    private int getLeftHeight(TreeNode root) {
        if (root == null)
            return 0;
        int height = 0;
        while (root.left != null) {
            height++;
            root = root.left;
        }
        return height;
    }
    
    private int getRightHeight(TreeNode root) {
        if (root == null)
            return 0;
        int height = 0;
        while (root.right != null) {
            height++;
            root = root.right;
        }
        return height;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        TreeNode n1 = new TreeNode(1);
        System.out.println(test.countNodes(n1));
    }
} 

My test result:


Paste_Image.png

这道题目最简单的做法,就是直接随便遍历。但肯定是不对的,太慢了。
我也在想办法,利用完整树的特性。
但是最后没做出来。
具体做法看下这个博客吧。写的很清楚。
http://www.programcreek.com/2014/06/leetcode-count-complete-tree-nodes-java/

programcreek 好网站

**
总结: 之前有道题目,kth Smallest number 也是采用了把树劈成两半,左右各自统计结点个数。
而这道题目,同样是左右各自遍历。虽然具体细节不同。
但是可以看出,这也算是树的遍历方式的一种。
Tree 免费的medium和easy差不多都做完了,还差两道easy。
感觉树的遍历方式有如下几种。
pre-order top-down
in-order sort-order for BST
post-order bottom-up

然后递归形式我可以很轻松地写出来。但是非递归形式不会写。
所以这三种遍历的非递归,要在这周末前学会写!!!!

然后,level-order
left to right
right to left
zigzag (use two stacks)

然后,
这道题目的遍历方式,分别遍历左子树与右子树,统计信息。
然后继续遍历左子树的左子树与右子树。。。。
以此循环。

同时,设置一些全局的私有变量,有时候会方便写代码。
**

Anyway, Good luck, Richardo!

My code:

/**
 * 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 countNodes(TreeNode root) {
        if (root == null)
            return 0;
        return helper(root);
    }
    
    private int helper(TreeNode root) {
        if (root == null)
            return 0;
        int left = getLeftDepth(root);
        int right = getRightDepth(root);
        if (left == right)
            return (int) (2 << (left - 1)) - 1;
        else
            return 1 + helper(root.left) + helper(root.right);
    }
    
    private int getLeftDepth(TreeNode root) {
        int counter = 0;
        while (root != null) {
            counter++;
            root = root.left;
        }
        return counter;
    }
    
    private int getRightDepth(TreeNode root) {
        int counter = 0;
        while (root != null) {
            counter++;
            root = root.right;
        }
        return counter;
    }
}

这道题目第二次做还是没做出来。
就是用二分法做。
其中, 用左移位求 2 ^ n 速度更快。 如果用 Math.pow(2, n); 会超时。
参考网页:
http://www.programcreek.com/2014/06/leetcode-count-complete-tree-nodes-java/

另外,衍生出来一个问题,如果判断一棵树是不是complete
我写了一段代码如下:
My code:

public boolean isFullBT(TreeNode root) {
        if (root == null)
            return false;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        boolean totalNull = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                if (curr.left != null) {
                    if (totalNull)
                        return false;
                    q.offer(curr.left);
                }
                else if (curr.left == null) {
                    totalNull = true;
                }
                if (curr.right != null) {
                    if (totalNull)
                        return false;
                    q.offer(curr.right);
                }
                else if (curr.right == null) {
                    totalNull = true;
                }
            }
        }
        return true;
    }

自己写出来的。

可以参考下下面两个网页:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

http://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-2-recursive-solution/

Anyway, Good luck, Richardo!

My code:

/**
 * 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 countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int h = height(root);
        if (h == -1) {
            return 0;
        }
        else {
            int right = height(root.right);
            if (right == h - 1) {
                return (1 << h) + countNodes(root.right);
            }
            else {
                return (1 << (h - 1)) + countNodes(root.left);
            }
        }
    }
    
    private int height(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + height(root.left);
    }
}

这道题目我的做法超时了,即使换成 比特移位操作。
然后看了答案,觉得还是醍醐灌顶。

做大的变化在于右子树。
右子树高度和左子树之差,可能是0,可能是1
当差是0, 那么左子树一定会complete,那么我们可以用公式先计算出 左子树 + 根节点个数,然后recursion计算,右子树结点个数
当差是1,那么,右子树一定是complete tree,只不过高度少了1,移位的时候,少向右移动移位即可。然后我们需要recursive计算出,左子树的结点个数。
差不多就这么个思路。

iteration的做法也是如此:

My code:

/**
 * 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 countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int h = height(root);
        int ret = 0;
        while (root != null) {
            int right = height(root.right);
            if (right == h - 1) {
                ret += (1 << h);
                root = root.right;
            }
            else {
                ret += (1 << (h - 1));
                root = root.left;
            }
            h--;
        }
        
        return ret;
    }
    
    private int height(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + height(root.left);
    }
}

reference:
https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2

上一下我写的TLE的解法:

My code:

/**
 * 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 countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return helper(root);
    }
    
    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);
        int right = getMinDepth(root.right);
        if (left == right) {
            return (1 << (left + 1)) - 1;
        }
        else {
            int leftMin = getMinDepth(root.left);
            if (left == leftMin) {
                return (1 << left) + helper(root.right);
            }
            else {
                return helper(root.left) + 1 + helper(root.right);      
            }
        }
    }
    
    private int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
    }
    
    private int getMinDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        else {
            return Math.min(getMinDepth(root.left), getMinDepth(root.right)) + 1;
        }
    }
}

如何判断一棵树是否为complete?
就判断 左子树的最大深度和右子树的最小深度是否相等。
如果相等,就是complete

Anyway, Good luck, Richardo! -- 09/07/2016

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 总结类型: 完全子树(#222) BST(左右子树值的性质,注意不仅要满足parent-child relatio...
    __小赤佬__阅读 726评论 0 0
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,950评论 2 36
  • 目录 简书的 markdown 都不支持 [TOC] 语法……我就不贴目录了。下面按照类别,列出了29道关于二叉树...
    被称为L的男人阅读 3,383评论 0 8
  • 由OpenDigg 出品的前端开源项目周报第七期来啦。我们的前端开源周报集合了OpenDigg一周来新收录的优质的...
    OpenDigg阅读 424评论 1 2