Flatten binary tree to linked list

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Solution I: using stack, pre order traversal

public class Solution { public void flatten(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode p = root; while(p != null || !stack.empty()){ if(p.right != null){ stack.push(p.right); } if(p.left != null){ p.right = p.left; p.left = null; }else if(!stack.empty()){ TreeNode temp = stack.pop(); p.right=temp; } p = p.right; } } }

Solution II: in place

note the use of variable post

思路是先遍历右子树，然后左子树，最后根节点。这样的好处是遍历完一个子树后，子树里的所有左右孩子指针都不需要了。 递归调用返回该子树中第一个节点，用于后续调用的后继。

public class Solution { public void flatten(TreeNode root){ if (root == null){ return; } flat(root, null); } private TreeNode flat(TreeNode root, TreeNode post){ if (root == null){ return post; } TreeNode right = flat(root.right, post); TreeNode left = flat(root.left, right); root.right = left; root.left = null; return root; } }