java - "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

我接受的解决方案:

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 的最左边的节点。