题目：

Given a binary tree, flatten it to a linked list in-place.

For example,

Given

1        / \       2   5      / \   \     3   4   6

 

The flattened tree should look like:

1    \     2      \       3        \         4          \           5            \             6

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

链接： 

题解：

使用栈来辅助，很像先序遍历。也可以用recursive和Morris-travel。

Time Complexity - O(n)， Space Complexity - O(n)。

public class Solution {    public void flatten(TreeNode root) {        if(root == null)            return;        Stack
     
       stack = new Stack
      
       ();        TreeNode node = root;                while(node != null || !stack.isEmpty()){            if(node.right != null){                stack.push(node.right);            }            if(node.left != null){                node.right = node.left;                node.left = null;            } else {                if(!stack.isEmpty())                    node.right = stack.pop();            }            node = node.right;        }    }}
      
     

 

二刷：

先建立一个Stack<TreeNode>()， 再取得一个root的reference node。在root != null并且!stack.isEmpty()的情况下进行遍历。

假如右子树非空，则入栈。  

假如左子树非空，则将左子树放到右子树处，置空左子树。 否则左子树为空时，假如stack非空，则我们设置node.right = stack.pop();

将node移动一位 - node = node.right。

Discuss区有很多好解法。下次一定要补上recursive的。

Java:

Time Complexity - O(n)， Space Complexity - O(n)。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public void flatten(TreeNode root) {        Stack
     
       stack = new Stack<>();        TreeNode node = root;        while (node != null) {            if (node.right != null) stack.push(node.right);            if (node.left != null) {                node.right = node.left;                node.left = null;            } else if (!stack.isEmpty()){                node.right = stack.pop();            }            node = node.right;        }    }}
     

 

Reference:

https://leetcode.com/discuss/30719/my-short-post-order-traversal-java-solution-for-share

https://leetcode.com/discuss/17944/accepted-simple-java-solution-iterative

https://leetcode.com/discuss/27643/straightforward-java-solution

https://leetcode.com/discuss/13054/share-my-simple-non-recursive-solution-o-1-space-complexity