仅将所有 List 元素添加到树的 RightNode

Question

我创建了一个链表并在上面添加了一些元素。现在我想将 LinkedList 中的所有元素添加到 Tree。仅在 RightNode 上。左节点将为空。树将如下所示--

我写了下面的代码。但是它覆盖了它的节点。没有给出正确的输出。我的代码如下 --

我的二叉树是--

  public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
     }
  }

    Queue<Integer> lst = new LinkedList<>();        
    
    lst.add(10);
    lst.add(20);
    lst.add(30);
    lst.add(40);
    
    TreeNode nRoot=null;
    
    while(!lst.isEmpty()){                      
        
        if(nRoot==null)
            nRoot = new TreeNode(lst.poll());
        else{
            nRoot.right = new TreeNode(lst.poll());                        
            nRoot=nRoot.right;
        }
    }

给出输出 --

    Output - [10]
    Expected Output - [10,null,20,null,30,null,40]

请帮忙!!!

Answer 1

您缺少树的每个节点的“父节点”。所以你不能回到树的根元素。

所以你的代码应该是这样的：

public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode parent;
 TreeNode() {}
 TreeNode(int val) { this.val = val; }
 TreeNode(int val, TreeNode left, TreeNode right) {
   this.val = val;
   this.left = left;
   this.right = right;
 }
}

然后：

while(!lst.isEmpty()){                      
    
    if(nRoot==null)
        nRoot = new TreeNode(lst.poll());
    else{
        nRoot.right = new TreeNode(lst.poll());
        TreeNode parent=nRoot;                        
        nRoot=nRoot.right;
        nRoot.parent=parent;
    }
}

现在您可以通过这种方式打印您的树：

while(nRoot!=null){
 system.out.writeln(nRoot.val);
 nRoot=nRoot.parent;
}

仅将所有 List 元素添加到树的 RightNode

Add all List elements only to the RightNode of a Tree

java

algorithm

tree

binary-tree

data-structures