题目
给定一个二叉树,原地将它展开为链表。
例如,给定二叉树:
1 2 3 4 5
| 1 / \ 2 5 / \ \ 3 4 6
|
将其展开为:
1 2 3 4 5 6 7 8 9 10 11
| 1 \ 2 \ 3 \ 4 \ 5 \ 6
|
题解 + 思路
一开始想的是递归,但是递归是由底向顶递归生成,而这道题是由顶到底生成,虽然存在子问题,但是仍难以求解。
其实可以看做如下步骤:
- 找到左子树的最右节点。
1 2 3 4 5
| 1 / \ 2 5 / \ \ 3 4 6
|
- 将右子树移到左子树的最右节点。
1 2 3 4 5 6 7 8 9
| 1 / 2 / \ 3 4 \ 5 \ 6
|
- 右子树换为左子树,左子树置为 null
1 2 3 4 5 6 7 8 9
| 1 \ 2 / \ 3 4 \ 5 \ 6
|
- 从右节点开始,继续该操作
1 2 3 4 5 6 7 8 9 10 11
| 1 \ 2 \ 4 \ 5 \ 6 \ 3
|
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 26 27
|
class Solution { public void flatten(TreeNode root) { while(root!=null){ if(root.left==null){ root=root.right; }else{ TreeNode pre = root.left; while(pre.right!=null){ pre = pre.right; } pre.right = root.right; root.right = root.left; root.left = null; root = root.right; } } } }
|