计算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); 
}