LeetCode算法笔记-Day54
114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
|
方法一：前序遍历
Analyse:
将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。
Answer：
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
| /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
let preOrderList = [];
let dfs = (node)=>{
if(!!node){
preOrderList.push(node);
dfs(node.left);
dfs(node.right);
}
}
dfs(root);
for(let i=1;i<preOrderList.length;i++){
let _pre = preOrderList[i-1],_curr = preOrderList[i];
_pre.left = null;
_pre.right = _curr;
}
};
|
方法二 寻找前驱结点
Analyse:
对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。
Answer：
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
| /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
let curr = root;
while(curr !== null){
if(curr.left !== null){
const next = curr.left;
let pre = next;
while(pre.right !== null){
pre = pre.right;
}
pre.right = curr.right;
curr.left = null;
curr.right = next;
}
curr = curr.right;
}
};
|
