如何return顺序遍历指定子树的数组（指定节点的左子树或右子树）

Question

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

/**
 * 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);
}

Answer 1

H

/ --- \

L1----R1

/ \ ------ / \

L2

抱歉这棵丑陋的树，但是当你向左看时，你会在 L1 的左子节点 L2 上到达 null ptr。你上去，叫这个：

arrays[cur++] = node;

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

不过。当你用尽左子树时。您将转到右子树（头部为 R）。

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

如何return顺序遍历指定子树的数组（指定节点的左子树或右子树）

How to return an array of in order traversal of the specified subtree (left subtree or right subtree of specified node)

java

binary-tree