linked-list - 将 BST 转换为前序链表和后序链表

Question

这是第二轮亚马逊面试问题。将给定的二叉搜索树转换为前序和后序链表，并且此转换必须就地。

Answer 1

下面的代码是为了在不使用堆栈的情况下以预序遍历形式对二叉树进行扁平化而编写的。它采用前序遍历递归的方式。在此，TreeNode[] arr 将保存我正在更新该节点的右指针的最后一个最左边的节点值。

    public TreeNode preorderNode(TreeNode root,TreeNode[] arr)
    {
    if(root==null)
        return null;
    if(root!=null && root.left==null && root.right==null)    
        {
            arr[0]=root;
            return root;
        }
    TreeNode temp=root.right;
    if(root.left!=null)
        root.right=preorderNode(root.left,arr);
    else arr[0]=root;
    root.left=null;
    arr[0].right=preorderNode(temp,arr);
    return root;
    }
    public void flatten(TreeNode root) {

        if(root==null || (root.left==null && root.right==null))
            return;
        TreeNode temp=root.right;    
        TreeNode[] arr=new TreeNode[1];
        arr[0]=null;
        if(root.left!= null)
            root.right=preorderNode(root.left,arr);
        else
            arr[0]=root;
        root.left=null;
       arr[0].right=preorderNode(temp,arr);
   }