代码之家 › 专栏 › 技术社区 › Catie

统计bst中的左节点数

binary-tree

Catie · 技术社区 · 14 年前

给定一个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;
}

我知道这是错的,但我不知道为什么。有人能解释一下原因吗,也能帮我解答一下。

5 回复 | 直到 14 年前

Motti 14 年前

第二个递归分支覆盖第一个分支的值。另外,应该为左根添加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;
}

Marcelo Cantos 14 年前

不需要传播累加器( 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;
}

aioobe 14 年前

在你的第二行

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

放弃count的上一个值。也许应该是 += 而不是 = .

不过,我想这样表达:

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

Shamim Hafiz - MSFT 14 年前

我想你得重新构造一下你的代码。不要传递左节点的当前计数,只需从两个子节点接收并将它们相加即可。

paxdiablo 14 年前

我认为最优雅的解决方案是这个。是的,我当然有偏见。我是人类:-)

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

total = countLeft (root, 0)

通过向下传递左节点的指示符,它简化了必须向上传递的内容。下图显示了向上传递的每个和-从底部开始,每个空值向上传递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);
}