計算BST中左節點的數量

Question

給定一個BST，我需要找到樹的左節點數。

實施例：`

  +---+ 
      | 3 | 
      +---+ 
     / \ 
    +---+  +---+ 
    | 5 |  | 2 | 
    +---+  +---+ 
    /  / \ 
+---+  +---+  +---+ 
| 1 |  | 4 |  | 6 | 
+---+  +---+  +---+ 
     /
    +---+ 
    | 7 | 
    +---+` 

答案應該是4，如（5,1，4,7）是樹的所有左節點。

我在想什麼做的是：

public int countLeftNodes() { 
    return countLeftNodes(overallRoot, 0); 
} 

private int countLeftNodes(IntTreeNode overallRoot, int count) { 
    if (overallRoot != null) { 
     count += countLeftNodes(overallRoot.left, count++);  
     count = countLeftNodes(overallRoot.right, count); 
    } 
    return count; 
} 

我知道這是錯的，但我不知道爲什麼。有人可以解釋爲什麼，也可以幫我解答。

Answer 1

第二個遞歸分支覆蓋第一個值。你也應該爲左邊的根加1。

喜歡的東西：

private int countLeftNodes(IntTreeNode node) { 
    int count = 0; 
    if (node.left != null) 
     count += 1 + countLeftNodes(node.left);  

    if (node.right != null) 
     count += countLeftNodes(node.right); 


    return count; 
} 

Answer 2

在你的第二個行這裏

count += countLeftNodes(overallRoot.left, count++);  
count = countLeftNodes(overallRoot.right, count); 

你丟棄計數的前值。也許它應該是+=而不是=。

我會然而它表達出來是這樣的：

private int countLeftNodes(IntTreeNode root) { 
    return (root.left == null ? 0 : countLeftNodes(root.left) + 1) + 
      (root.right == null ? 0 : countLeftNodes(root.right)); 
} 

Answer 3

我認爲你必須調整你的一些代碼。而不是傳遞左節點的當前計數，只需從兩個孩子接收並添加它們即可。

Answer 4

因爲您不依賴尾遞歸，所以不需要將累加器（count參數）沿着調用堆棧向下傳播。

public int countLeftNodes(IntTreeNode node) { 
    // This test is only needed if the root node can be null. 
    if (node == null) return 0; 

    int count = 0; 
    if (node.left != null) { 
     count += 1 + countLeftNodes(node.left); 
    } 
    if (node.right != null) { 
     count += countLeftNodes(node.right); 
    } 
    return count; 
} 

Answer 5

我認爲最優雅的解決方案就是這個。是的，當然我有偏見。我是人類:-)

def countLeft (node,ind): 
    if node == null: return 0 
    return ind + countLeft (node->left, 1) + countLeft (node->right, 0) 

total = countLeft (root, 0) 

通過向下傳遞左節點的指標，它簡化了必須傳遞的內容。下圖顯示了每個傳遞的總和 - 您從底部開始，每個null都遞增0.

左側的每個節點都會傳遞1以及來自兩個分支的任何節點。右側的每個節點都會傳遞0加上來自兩個分支的任何節點。

根本沒有增加任何東西，因爲它既不是左邊節點也不是右邊節點（它的處理方式與右邊相同）。

     4 
         ^
         | 
         +---+ 
         | 3 | 
      __________+---+__________ 
      /2      2\ 
     +---+       +---+ 
     | 5 |       | 2 | 
     +---+       +---+ 
    /1        /2 0\ 
+---+       +---+  +---+ 
| 1 |       | 4 |  | 6 | 
+---+       +---+  +---+ 
/0 0\      /1 0\  /0 0\ 
          +---+ 
          | 7 | 
          +---+ 
         /0 0\ 

---

你可以從這個完整的程序見操作：

#include <stdio.h> 

typedef struct sNode { int val; struct sNode *left, *right; } tNode; 

#define setNode(N,V,L,R) N.val = V; N.left = L; N.right = R 

int countLeft (tNode *node, int ind) { 
    if (node == NULL) return 0; 
    int x = ind + countLeft (node->left, 1) + countLeft (node->right, 0); 
    printf ("Node %d passing up %d\n", node->val, x); 
    return x; 
} 

int main (void) { 
    tNode n3, n5, n1, n2, n4, n6, n7; 
    setNode (n3, 3, &n5, &n2); 
    setNode (n5, 5, &n1, NULL); 
    setNode (n1, 1, NULL, NULL); 
    setNode (n2, 2, &n4, &n6); 
    setNode (n4, 4, &n7, NULL); 
    setNode (n7, 7, NULL, NULL); 
    setNode (n6, 6, NULL, NULL); 

    printf ("countLeft is %d\n", countLeft (&n3, 0)); 
    return 0; 
} 

，它輸出的調試線路：

Node 1 passing up 1 
Node 5 passing up 2 
Node 7 passing up 1 
Node 4 passing up 2 
Node 6 passing up 0 
Node 2 passing up 2 
Node 3 passing up 4 
countLeft is 4 

的countLeft函數的非調試版本就像這個答案開始時的僞代碼一樣簡單：

int countLeft (tNode *node, int ind) { 
    if (node == NULL) return 0; 
    return ind + countLeft (node->left, 1) + countLeft (node->right, 0); 
}