Given a binary tree, flatten it to a linked list in-place
我的想法是，先将左子树flatten，然后右子树flatten，然后将左子树的结果移到root.right，然后将右子树接在左子树后面。但是总是超时。
1 public static void flatten(TreeNode root) { 2 if (root == null) return; 3 TreeNode left = root.left; 4 TreeNode right = root.right; 5 flatten(left); 6 flatten(right); 7 if (left != null) { 8 root.right = left; 9 while(left.right != null) { 10 left = left.right; 11 } 12 left.right = right; 13 } 14 15 return; 16 }
网上看的方法是，先将左子树移到root.right，然后把右子树接在后面，最后在flatten整个右子树。。。
1 public void flatten(TreeNode root) { 2 if(root == null){ 3 return; 4 } 5 6 if(root.left != null){ 7 TreeNode rightNode = root.right; 8 TreeNode leftNode = root.left; 9 root.left = null; 10 root.right = leftNode; 11 TreeNode p = leftNode; 12 while(p.right != null){ 13 p = p.right; 14 } 15 p.right = rightNode; 16 } 17 flatten(root.right); 18 }
LeetCode: Flatten Binary Tree to Linked List
原文：http://www.cnblogs.com/longhorn/p/3542228.html