题目链接:
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
解法分析:
解法一:前序遍历

由图示可知,树扯直以后特征是:每个左孩子为空,右孩子为前序遍历的下一位
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 28 29 30
|
var flatten = function(root) { const list = []; preorderTraversal(root);
for (let i = 1; i < list.length; i++) { const pre = list[i - 1], cur = list[i]; pre.left = null; pre.right = cur; }
function preorderTraversal(root) { if (!root) return;
list.push(root); preorderTraversal(root.left); preorderTraversal(root.right); } };
|
解法二:递归

把树拉直的步骤可归为以下三步:
- 将左子树和右子树扯直

- 将右子树换成左子树

- 将原来的右子树接到当前右子树的后面

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 28 29 30 31 32 33 34 35
|
var flatten = function(root) { if (!root) { return; }
flatten(root.left); flatten(root.right);
const leftTree = root.left, rightTree = root.right;
root.right = leftTree; root.left = null;
let p = root; while (p.right) { p = p.right; }
p.right = rightTree; };
|
参考题解:
- https://labuladong.gitee.io/algo/2/17/21/
- https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/