leetcode222. Count Complete Tree Nodes

crossoverJie 发布于2019-08-16 12:11 / 2446人阅读

摘要：题目要求计算一个完全二叉树的节点个数。其中完全二叉树是指除了最后一行，其余的每一行都必须是满节点的树。当然超时啦思路二讲道理的递归思路一很明显没有充分利用这是一颗完全二叉树的条件。

题目要求

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

计算一个完全二叉树的节点个数。其中完全二叉树是指除了最后一行，其余的每一行都必须是满节点的树。

思路一：不讲道理的递归

直接返回左子树和右子树的叶结点的个数。当然超时啦

    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

思路二：讲道理的递归

思路一很明显没有充分利用这是一颗完全二叉树的条件。从另一个角度看，一颗完全二叉树的左子树和右子树有两种情况

左子树比右子树高

左子树和右子树一样高

当左子树和右子树一样高时，说明左子树本身是一颗满二叉树，它的元素个数为2^h左-1。
当左子树比右子树高时，说明右子树本身是一颗满二叉树，它的元素个数为2^h右-1(h为树的高度)

所以每一次通过判断左右子树的高度可以得到其中一棵子树的元素个数，这时再递归到另一颗子树继续计算直到当前元素为null。
代码如下：

    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes2(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes2(root.right)
                                         : (1 << h-1) + countNodes2(root.left);
    }

思路三：递什么归！

当递归转化为循环且该循环并不需要使用栈这种数据结构时，性能往往会得到质的飞跃。在上面的思路二中采用递归，在这里我们将递归转变为循环。同时我们只需要计算一次树的高度，因为每一次选择的子树的高度都是上一个高度-1。

    int height2(TreeNode root){
        if(root==null) return -1;
        int height = 0;
        while(root.left!=null) {height++; root=root.left;}
        return height;
    }
    
    public int countNodes3(TreeNode root) {
        int count = 0;
        int height = height2(root);
        while(root!=null){
            if(height2(root.right)==height-1){
                count += 1<

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Nodes complete 222cc cc222

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71145.html

[LeetCode] 222. Count Complete Tree Nodes

Problem Given a complete binary tree, count the number of nodes. Note: Definition of a complete binary tree from Wikipedia:In a complete binary tree every level, except possibly the last, is completel...

kamushin233 2019-08-16 13:54 评论0 收藏0
222. Count Complete Tree Nodes

摘要：题目解答学了的方法哈哈这里是从开始算起，所以求出来的结果是实际是这一步很巧妙，把根结点加上，然后分治左结点和右结点，如果是叶子结点，在中就返回题目：Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from Wikipedia:In a compl...

callmewhy 2019-08-14 14:14 评论0 收藏0
[Leetcode] Count Complete Tree Nodes 统计完全树节点数

摘要：如果不等于，则是左子树的节点数，加上右子树的节点数，加上自身这一个。注意这里在左节点递归时代入了上次计算的左子树最左深度减，右节点递归的时候代入了上次计算的右子树最右深度减，可以避免重复计算这些深度做的幂时不要用，这样会超时。 Count Complete Tree Nodes Given a complete binary tree, count the number of nod...

animabear 2019-08-14 12:41 评论0 收藏0
[LeetCode] 501. Find Mode in Binary Search Tree

Problem Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node c...

NikoManiac 2019-08-16 13:51 评论0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 评论0 收藏0