将二叉树转换为只有叶节点的链表

Question

这就是问题。

给定一棵二叉树，我们需要用叶节点制作链表。限制是它应该使用额外的 O(1) space 来完成。也可以用节点->右指针来连接链表。

给出下面的树。

      10

 5           12
     7   11      15

结果应该是：

           10

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

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

这是我尝试过的：

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

由于只需要添加叶子节点，即下面的条件要成为叶节点 - 它不应该有左右节点，即 root.left & root.right 应该为 null

我想你需要做一个 && 条件，如下所示

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

注意：这还没有经过测试。

将二叉树转换为只有叶节点的链表

convert binaryTree to LinkedList with only Leaf Nodes

java

algorithm

binary-tree

linked-list