将新分支添加到树中，然后以有效的方式将新叶子添加到链表中的正确位置

Question

假设我们有一个二叉树和一个链表，其中包含出现在所有叶子中的数据。

例如，以下树的列表将是：9,2,3（顺序很重要，从左到右）

现在我们在某处添加一个新节点，从而创建一个新分支，如下所示：

有没有一种有效的方法可以将这个新叶子添加到列表中，使列表保持叶子从左到右的顺序？即新列表应该是 9,1,2,3.

我想出的任何东西，在最坏的情况下，都等同于制作一个全新的列表，即遍历整棵树。

就像在 LDR 中遍历树并在保留最后一片叶子的信息的同时寻找新叶子，但在最坏的情况下它可能会遍历整个或大部分树。

顺便说一句，列表和树是这样任意定义的：

typedef struct listNode  {
    int data;
    struct listNode* next;
} ListNode;

typedef struct  treeNode {
    int data;
    struct treeNode* parent; //prev node
    struct treeNode* left;
    struct treeNode* right;
} TreeNode;

Answer 1

是的，但它还需要向 treeNode 添加更多数据，指向列表节点的指针（如果存在）。

现在，一旦您找到添加新节点 (v) 的位置，假设它是某个节点 u 的子节点。
您需要找到上一页。它可以在 O(h) 中通过在树上向上移动来完成，直到找到一个有左儿子的节点 x。到左儿子处，继续遍历，顺序如下：

if the current node has right son:
     go to right son, repeat
else if the current node has left son:
     go to left son, repeat
else:
     found previous leaf, let it be l

现在，您有了新节点 v 和前一个叶子节点 l。

你现在要做的就是将v的节点放在l的节点之后：

v.node = createNode();
v.node.next = l.node.next; 
l.node.next = v.node;

此算法的复杂度为 O(h)，其中 h 是树的高度。

注意：注意简单的边缘情况，其中 v 是链表中的第一个节点。

将新分支添加到树中，然后以有效的方式将新叶子添加到链表中的正确位置

Adding a new branch to a tree then adding the new leaf to the right place in a linked list in an efficient way

c

algorithm

tree

binary-tree