时间戳

首页 > 解决方案 > 如何返回按顺序遍历指定子树（指定节点的左子树或右子树）的数组

java - 如何返回按顺序遍历指定子树（指定节点的左子树或右子树）的数组

问题描述

我使用递归函数实现它，如下所示。我很确定我以正确的顺序实现它，但是我似乎未能通过我的测试用例，有人可以指出我的代码哪里出了问题吗？

/**
 * Build an array of nodes in the specified subtree.
 *
 * @param node  the parent node, not to be included in returned array
 * @param child the specified subtree
 * @return array of nodes
 */
//countNodes return the total number of nodes in the subtree excluding the parent node

public TreeNode[] enumerateNodes(TreeNode node, Child child) {
    TreeNode[] treeNodes = new TreeNode[countNodes(node, child)];
    if(child == Child.RIGHT) {
        node = node.right;
    }
    if(child == Child.LEFT) {
        node = node.left;
    }
    enumerateNodes(node, treeNodes, 0);
    return treeNodes;
}
private void enumerateNodes(TreeNode node, TreeNode[] arrays, int cur){
    if(node == null){
        return;
    }
    enumerateNodes(node.left, arrays, cur);
    arrays[cur++] = node;
    enumerateNodes(node.right, arrays, cur);
}

标签： javabinary-tree

解决方案

H

/ --- \

L1 ---- R1

/ \ ------ / \

L2

抱歉这棵丑陋的树，但是当你向左走时，你会看到 L1 的左孩子的空 ptr 是 L2。你上去，叫这个：

arrays[cur++] = node;

现在 cur 得到 0，数组将 L2 作为第一个节点（索引 0）。将递增到 1。使用正确的值向右移动。到目前为止一切都很好。

然而。当你用尽左子树时。您将转到右子树（带有头 R）。

array[0] = L1 // this will override L2

推荐阅读