「計數完成樹節點」 - 如何優化解決方案？

我已經寫了一個解決這個問題： 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; } 
* } 
*/

來源

2015-10-16 anirban.at.web

這個網站是爲解決發展過程中出現的錯誤。你的問題更適合[codereview.se]。 –

在靜態計數（）方法，你只計算節點到左邊，而不是權利。作爲完整性的一部分，您可能會錯過正確的數字。 –

@GeraldSchneider我不知道那個網站。我一定會在未來發布。 –

我接受的解決方案：

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

來源

2015-10-16 11:50:13

另一個'的log（n）*的log（n）'解決辦法，但比我短。 – Sayakiss

讓我告訴你的思維方式。

首先，我們定義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。

來源

2015-10-16 11:48:51 Sayakiss

似乎(int)(Math.pow(2, left)-1)和(int)(Math.pow(2, right)-1)只是太慢。只要將它們更改爲

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

並且您將接受您的代碼。

來源

2015-10-16 12:23:00 svs

「計數完成樹節點」 - 如何優化解決方案？

回答

相關問題