转换binaryTree到LinkedList只有叶节点

Question

这就是问题所在。

给定一棵二叉树，我们需要从叶子节点中生成链表。约束条件是它应该使用O(1)个额外空间来完成。也可以使用node->右指针来连接链表。

给定下面的树。

      10
 5           12
     7   11      15

结果应该是:

           10
     5           12
 L ->   7 -> 11  ->   15

注意L是一个新的指针，它引用了leafnode，每个leafnode都有正确的指针指向它们。

这是我尝试的:

public class TreeManipulationMethods {
    private static IntTreeNode linkedlist=null;
    private static IntTreeNode prev=null;
    private static int preIndex=0;
    private static Node headNode;

   public static void main(String[] args){
      IntTreeNode tree1=new IntTreeNode(10);
        tree1.left=new IntTreeNode(5);
        tree1.left.right=new IntTreeNode(7);
        tree1.right=new IntTreeNode(12);
        tree1.right.left=new IntTreeNode(11);
        tree1.right.right=new IntTreeNode(15);
       convertToLinkedListWithOnlyLeafNodes(tree1);
        linkedlist.printRight();
    }
    public static void convertToLinkedListWithOnlyLeafNodes(IntTreeNode root){
        if (root==null)
            return;
        convertToLinkedListWithOnlyLeafNodes(root.left);
        if (isLeaf(root)){
             if (linkedlist==null)
                 linkedlist=root;
             else 
                 prev.right=root;
             prev=root;
        }
        convertToLinkedListWithOnlyLeafNodes(root.right);
    }
  private static boolean isLeaf(IntTreeNode root){
        return root!=null || (root.left==null && root.right==null);
    }
}
class IntTreeNode {
    int val;
    IntTreeNode right;
    IntTreeNode left;
    public IntTreeNode(int val){
        this.val=val;
    }
    public void printRight(){
        String toRet="[ ";
        IntTreeNode current = this;
        while(current!=null){
            toRet+=current.val + " -> ";
            current=current.right;
        }
        toRet+="NULL ]";
        System.out.println(toRet);
    }
}

输出如下:[ 5 -> 7 -> 10 -> 11 -> 12 -> 15 -> NULL ]

这显然是不正确的。

预期的输出将是[7->11->15]

Answer 1

由于您只需要添加叶节点，即以下是条件作为叶节点，它不应该留下&右节点即根节点。离开了,根。Right应为null

我猜你需要做一个&&条件，如下面

 root!=null && (root.left==null && root.right==null)