Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
The flattened tree should look like:
1 2 3 4 5 6 7 8 9 10 11
|
1 2 3 4 5 6
|
Code
1 2 3 4 5 6
|
public class { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
public void flatten(TreeNode root) { helper(root); }
private TreeNode helper(TreeNode root) { if (root == null) return null;
TreeNode leftTail = helper(root.left); TreeNode rightTail = helper(root.right);
if (root.left != null) { TreeNode temp = root.right; root.right = root.left; root.left = null; leftTail.right = temp; }
if (rightTail != null) return rightTail; else if (leftTail != null) return leftTail; else return root; }
|
近期评论