Voyz's Studio.

LeetCode算法笔记--二叉树展开为链表

字数统计: 465阅读时长: 2 min
2020/12/31 Share

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;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法二 寻找前驱结点

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;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
CATALOG
  1. 1. LeetCode算法笔记-Day54
    1. 1.1. 114. Flatten Binary Tree to Linked List
    2. 1.2. 方法一:前序遍历
      1. 1.2.1. Analyse:
      2. 1.2.2. Answer:
    3. 1.3. 方法二 寻找前驱结点
      1. 1.3.1. Analyse:
      2. 1.3.2. Answer: