"Count Complete Tree Nodes" - 如何优化解决方案？

Question

我已经为这个问题写了一个解决方案： https://leetcode.com/problems/count-complete-tree-nodes/
但我得到了 TLE。我该如何优化它？

public class Solution 
{
    public int countNodes(TreeNode root) 
    {
        if(root==null)
            return 0;
        int left = count(root.left);
        int right = count(root.right);
        if(left<=right)
        {
            return ((int)(Math.pow(2, left)-1) + countNodes(root.right) + 1);
        }
        else
        {
            return (countNodes(root.left) + (int)(Math.pow(2, right)-1) + 1);
        }
    }

    public static int count(TreeNode root)
    {
        int ctr=0;
        while(root!=null)
        {
            ctr++;
            root = root.left;
        }
        return ctr;
    }
}

树在 OJ 中定义为：

/**
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Answer 1

让我告诉你思考的方式。

首先，我们定义countLevel(TreeNode tree) - return the level of the binary tree.

我们在：

countLevel(TreeNode tree):
  if (tree.isNoChild()) 
    return 1;
  else 
    return countLevel(tree.left) + 1;
  // countLevel(tree.right) always less than or equals countLevel(tree.left) in complete binary tree

如果我们知道级别是 i，那么我们可以知道节点数在 [2^(i-1), 2^i - 1].

之间

在我们尝试解决原点问题之后，我们先解决一个更容易的问题：

isNodesMoreThan(TreeNode tree, int n) - does tree have n nodes or more?

你应该尝试解决这个问题，它可以在log(n)（n是输入树的节点数）中完成。

如果你解决了isNodesMoreThan，通过二进制搜索，你可以得到log(n)*log(n)中树的节点数，这不会得到TLE。

Answer 2

我接受的解决方案：

public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int h = 0;
        TreeNode node = root;
        while(node != null){
            h++;
            node = node.left;
        }
        return count(h, root);
    }

    public int count(int h, TreeNode node){
        if(node == null){
            return 0;
        }
        int v = heightRight(node.left);
        if(v == h - 1){
            return  (1 << (h - 1)) + count(h - 1, node.right);
            //The left subtree is a perfect binary tree with height h - 1
            //So, we only need to look at the right subtree
        }else {
            return (1 << (h - 2)) + count(h - 1, node.left);
            //The right subtree is perfect binary tree with height h - 2
            //So, we only need to look at the left subtree
        }
    }

    public int heightRight(TreeNode node){
        if(node == null){
            return 0;
        }
        int result = 0;
        while(node != null){
            node = node.right;
            result++;
        }
        return result;
    }
}

所以，我们可以通过应用类似于二分查找的技术来解决这个问题。

由于完全二叉搜索树几乎是完美的二叉树，除了最后一层，所以，

若树的高度为h，则左子树的高度为h - 1，右子树的高度在[h - 2, h - 1]之间。

-> 我们需要做的是找到高度为 h - 2 的最左边的节点。

Answer 3

似乎 (int)(Math.pow(2, left)-1) 和 (int)(Math.pow(2, right)-1) 太慢了。只需将它们更改为

(1 << left) - 1
(1 << right) - 1

您的代码将被接受。

"Count Complete Tree Nodes" - 如何优化解决方案？

"Count Complete Tree Nodes" - How to optimize the solution?

java

algorithm

tree

binary-tree

data-structures