Flatten Binary Tree to Linked List
Oct 14 '12
7105 / 21371
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
其实就是前序遍历,还可以考虑非递归的方式
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void flatten(TreeNode root) { if(root ==null) return; find(root); } public TreeNode find(TreeNode root){ if(root==null) return null; TreeNode last =null; TreeNode left = root.left,right = root.right; if(root.left==null && root.right==null) return root; if(root.left!=null){ root.right = left; root.left = null; last = find(left); last.right = right; } if(right!=null) last = find(right); return last; } }