如何编写'addToRightMostChildAsLeftChild（节点a，节点b）'的代码？

Question

让我们说上面的方法有两个参数a and b：

• a：表示我们需要遍历的树的根节点，直到我们得到正确的节点
• b：表示要作为左子节点添加到最右侧节点的节点。

我只需要知道如何将`节点添加到树的最右边节点但是作为左子节点。我实际上正在解决不同版本的this问题。这里的问题是使用正确的指针。

以这样的方式构造树，即仅通过左指针遍历它生成树的预顺序遍历。

实际上它可以通过遍历树并保持previous node and linking them in the way we want :prev.left = current`来解决。

我解决这个问题的方法是：如果有一棵树如下

（只需将节点2到5添加为左子节点，然后将5到3添加为左子节点，最后将6到4添加为左子节点。）

                 10
                 / \
                8   2
               / \ / \
              3  5 4  6


               10
               /
              8
             / \
            3   5
               /
              2
             / \
            4   6

             10
             /
            8
           / 
          3
         /
        5
       /
      2 
     / \
    4   6
             10
             /
            8
           / 
          3
         /
        5
       /
      2
     /
    4
   /
  6

10 8 3 5 2 4 6这是树的pre-order traversal

我知道它可以通过使用`prev指针和做东西来完成。我想要这样做。

                 10        
                 / \
                8   2      
               / \ / \
              3  5 4  6

                 ||
                 \/

                10
               /
              8
             / 
            3
           /
          5
         /
        2
       /
      4
     /
    6

节点定义为：

 class Node{
    int data;
    Node left,right;
    Node(int d)
    {
        data=d;
        left=null;
        right=null;
    }
}

Answer 1

在考虑之后我能够做到这一点。

void addToRightMostNodeAsLeftChild(Node root,Node toBeAdded)
{
    if(root.left==null)
    {
        root.left=toBeAdded;
    }
    else
    {
        Node k=getRMNode(root.left);
        if(k.left==null)
        {
            k.left=toBeAdded;
        }
        else
            addToRightMostNodeAsLeftChild(k, toBeAdded);
    }
    root.right=null;
}

那么，当我想将节点2作为5的左子节点放置时，它是节点8的最右边的节点（在这里将一个XYZ节点XYZ的最右边节点作为左子节点添加为8）当调用该方法时如下：

addToRightMostNodeAsLeftChild(root,X) /*root represents node 10 and X represents node 2*/

它被转换为：

           10
           /
          8
         / \
        3   5
           /
          2
         / \
        4   6