例如,给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为:
1
\
2
\
3
\
4
\
5
\
6
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
// 前序遍历将所有节点塞入数组,遍历数组,让每个节点的left变成null right指向下一个节点
var flatten = function(root) {
const list = [];
pre(root, list);
for (let i = 0; i < list.length - 1; i++) {
list[i].left = null;
list[i].right = list[i + 1];
}
return list[0];
};
function pre(root, list) {
if (!root) {
return;
}
list.push(root);
pre(root.left, list);
pre(root.right, list);
}
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
// 1.将一个节点的左右子树转换为单链表 2.将右子树插入到左子树的末尾 3,左子树变成右子树 4.左子树置为null
var flatten = function(root) {
if (root === null) {
return;
}
// 第1步
flatten(root.left);
flatten(root.right);
// 左子树为null就不需要处理了
if (root.left === null) {
return;
}
//第2步
let end = root.left;
while(end && end.right) {
end = end.right;
}
end.right = root.right
//第3 第4步
root.right = root.left;
root.left = null;
return root;
};