Flatten Binary Tree to Linked List 453

Question

Flatten a binary tree to a fake "linked list" in pre-order traversal.

Here we use the right pointer in TreeNode as the next pointer in ListNode.

Notice

Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

Example

          1
           \
 1          2
/ \          \

2 5 => 3 / \ \ \ 3 4 6 4 \ 5 \ 6 Challenge

Do it in-place without any extra memory.

Solution

递归方法：Divide and Conquer.

非递归方法：用stack实现。将root加入stack后，出栈时，现将right加入，再将left加入。然后将出栈元素的left设为null，如果此事stack为空（即出栈元素为最后一个元素），则出栈元素的right也设为null；如果不为空，则将栈顶元素（即出栈元素的原left）设为出栈元素的right。

代码如下：

Recursion Version

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        // write your code here

        helper(root);
    }

    private TreeNode helper(TreeNode root){
        if(root == null || (root.left == null && root.right == null)){
            return root;
        }

        if(root.left == null){
            return helper(root.right);
        }

        if(root.right == null){
            root.right = root.left;
            root.left = null;
            return helper(root.right);
        }

        TreeNode leftLast = helper(root.left);
        TreeNode rightLast = helper(root.right);

        leftLast.right = root.right;
        root.right = root.left;
        root.left = null;
        return rightLast;
    }
}

Non-Recursion Version

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        // write your code here
        //Non-Recursion Version
        if(root == null || (root.left == null && root.right == null)){
            return;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curt = stack.pop();

            if(curt.right != null){
                stack.push(curt.right);
            }

            if(curt.left != null){
                stack.push(curt.left);
            }

            curt.left = null;
            if(stack.isEmpty()){
                curt.right = null;
            }else{
                curt.right = stack.peek();
            }
        }
    }