java - 如何编写“addToRightMostChildAsLeftChild(Node a,Node b)”的代码？

Question

假设上述方法有两个参数a and b：

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

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

以这样一种方式构造一棵树，即仅通过左指针遍历它会生成树的前序遍历。

实际上它可以通过遍历树并保持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;
    }
}

标签： javabinary-treetraversal

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