二叉树的遍历
# 二叉树的遍历
# lc144. 二叉树的前序遍历简单 hot
题目描述
给你二叉树的根节点 root
,返回它节点值的 前序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,2,3]
2
示例 2:
输入:root = []
输出:[]
2
示例 3:
输入:root = [1]
输出:[1]
2
示例 4:
输入:root = [1,2]
输出:[1,2]
2
示例 5:
输入:root = [1,null,2]
输出:[1,2]
2
法一: 递归
思路很简单就是先递归遍历左子树再遍历右子树
时间复杂度O(n)
空间复杂度O(n)
/**
* 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 {number[]}
*/
var preorderTraversal = function(root) {
let result = []
const childNode = (node) => {
if(node) {
result.push(node.val)
childNode(node.left)
childNode(node.right)
// 同样的,中序遍历则是先left 再push 再right
// 后序遍历则是 先left 后right 再push
}
}
childNode(root)
return result
};
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
法二:迭代
用栈来模拟递归
维护一个栈数组和一个结果数组
首先根节点入栈
由于栈是后进先出
首先根节点出栈,将根节点的值放在结果数组中
如果该根节点存在右节点,让右节点入栈
接着如果该根节点存在左节点,左节点入栈
var preorderTraversal = function(root) {
const stack = []
const list = []
if(root) stack.push(root)
while(stack.length > 0) {
const curNode = stack.pop()
list.push(curNode.val)
if(curNode.right) stack.push(curNode.right)
if(curNode.left) stack.push(curNode.left)
}
return list
};
// 中序遍历
var inorderTraversal = function(root) {
const stack = []
const list = []
while(stack.length || root) {
while(root) {
stack.push(root)
root = root.left
}
root = stack.pop()
list.push(root.val)
root = root.right
}
return list
}
// 后序遍历
var postorderTraversal = function(root) {
if(!root) return []
const res = []
const stack = []
stack.push(root)
while(stack.length) {
let node = stack.pop()
res.unshift(node.val)
if(node.left) stack.push(node.left)
if(node.right) stack.push(node.right)
}
return res
}
// 或者模仿一下先序遍历的递归
// 先序遍历是一个栈 root 进,然后右,然后左,然后出栈 [根,左,右]
// 后序遍历要得到[左,右,根],那么就得到[根,右,左],再翻转
var postorderTraversal = function(root) {
const stack = []
const list = []
if(root) stack.push(root)
while(stack.length > 0) {
const curNode = stack.pop();
list.push(curNode.val);
if(curNode.left) stack.push(curNode.left);
if(curNode.right) stack.push(curNode.right);
}
return list;
};
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
时间复杂度O(n)
空间复杂度O(n)
# lc589. N叉树的前序遍历简单
题目描述
给定一个 N 叉树,返回其节点值的 前序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。
进阶:
递归法很简单,你可以使用迭代法完成此题吗?
示例 1:

输入:root = [1,null,3,2,4,null,5,6]
输出:[1,3,5,6,2,4]
2
3
示例 2:

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
2
3
// 递归
/**
* @param {Node|null} root
* @return {number[]}
*/
var preorder = function(root) {
const res = []
const childNode = node => {
if(node) {
res.push(node.val)
node.children.forEach(item => {
childNode(item)
})
}
}
childNode(root)
return res
};
// 迭代
var preorder = function(root) {
const stack = []
const res = []
if(root) stack.push(root)
while(stack.length) {
let node = stack.pop()
res.push(node.val)
if(node.children) {
for(let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i])
}
}
}
return res
};
// N叉🌲后序遍历
var postorderTraversal = function(root) {
if(!root) return []
const res = []
const stack = []
stack.push(root)
while(stack.length) {
let node = stack.pop()
res.unshift(node.val)
if(node.children) {
stack.push(...node.children)
}
}
return res
};
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# lc102. 二叉树的层序遍历中等hot
题目描述
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
2
3
4
5
6
返回其层序遍历结果:
[
[3],
[9,20],
[15,7]
]
2
3
4
5
法一:BFS广度优先
思路:
- 每向下一层,然后把他们的值存起来
- 利用了多个数组
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
if(!root) return [];
const queue = [root];
const res = [];
let depth = 0;
while (queue.length) {
res[depth] = res[depth] || []
// 这个queue保存了当前深度的所有节点
const size = queue.length;
// 把当前深度的节点的左右节点推进queue中,那就是下一个深度的所有节点
for(let i = 0; i < size; i++) {
const node = queue.shift();
res[depth].push(node.val);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
depth++;
}
return res;
};
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
时间复杂度O(n)
空间复杂度O(n)
法二:DFS深度优先
- 根据树依次向下遍历,并记录每次的
depth
- 然后把相应的
node.val
存到结果数组里面去
/**
* 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 {number[][]}
*/
var levelOrder = function(root) {
let res = []
const dep = function(node, depth) {
if(!node) return
res[depth] = res[depth] || []
res[depth].push(node.val)
dep(node.left, depth + 1)
dep(node.right, depth + 1)
}
dep(root, 0)
return res
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
时间复杂度O(n)
空间复杂度O(h)
h
为树的高度
# lc103. 二叉树的锯齿形层序遍历中等hot
题目描述
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
2
3
4
5
6
7
返回锯齿形层序遍历如下:
[
[3],
[20,9],
[15,7]
]
2
3
4
5
思路
就是从零开始,奇数就从右往左,偶数就从左往右
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
const res = []
function dfs(node, depth){
if(!node) return
if(!Array.isArray(res[depth])){
res[depth] = []
}
// 奇数
if(depth & 1){
res[depth].unshift(node.val)
}else{
res[depth].push(node.val)
}
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
}
dfs(root, 0)
return res
};
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
时间复杂度O(n)
空间复杂度O(n)
# lc958. 二叉树的完全性检验中等hot
题目描述
给定一个二叉树,确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下:
若设二叉树的深度为 h
,除第 h
层外,其它各层 (1~h-1)
的结点数都达到最大个数,第 h
层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h
层可能包含 1~ 2h
个节点。)
示例 1:
输入:[1,2,3,4,5,6]
输出:true
解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),且最后一层中的所有结点({4,5,6})都尽可能地向左。
2
3
4
5
示例 2:
输入:[1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。
2
3
4
5
思路
使用队列层序遍历。
遇到非空节点就继续将其左右孩子加入队列。
遇到空节点后,设一个标记 end = true
。
如果后续还遇到非空节点,则返回 false
。
var isCompleteTree = function(root) {
let queue = [root];
let end = false;
while (queue.length > 0) {
let node = queue.shift();
if (!node) {
end = true;
} else {
if (end) return false;
queue.push(node.left);
queue.push(node.right);
}
}
return true;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
时间复杂度O(n)
空间复杂度O(1)
只用初始化一个队列 为常数个内存
# lc114. 二叉树的展开为链表中等
题目描述
给你二叉树的根结点 root
,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode
,其中 right
子指针指向链表中下一个结点,而左子指针始终为 null
。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]
2
3
示例 2:
输入:root = []
输出:[]
2
3
示例 3:
输入:root = [0]
输出:[0]
2
3
var flatten = function(root) {
const res = []
const childNode = node => {
if(node) {
res.push(node)
childNode(node.left)
childNode(node.right)
}
}
childNode(root)
for(let i = 0; i < res.length - 1; i++) {
res[i].left = null
res[i].right = res[i + 1]
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- 时间复杂度:
O(n)
,其中n
是二叉树的节点数。前序遍历的时间复杂度是O(n)
,前序遍历之后,需要对每个节点更新左右子节点的信息,时间复杂度也是O(n)
。 - 空间复杂度:
O(n)
,其中n
是二叉树的节点数。空间复杂度取决于栈(递归调用栈或者迭代中显性使用的栈)和存储前序遍历结果的列表的大小,栈内的元素个数不会超过n
,前序遍历列表中的元素个数是n
。
原地操作, 栈模拟先序遍历
function flatten(root) {
if (!root) return;
const stack = [root];
let prev = null;
while (stack.length) {
const node = stack.pop();
if (prev) {
prev.right = node;
prev.left = null;
}
// 先右后左入栈,保证先序遍历顺序
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
prev = node;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 129. 求根节点到叶节点数字之和中等hot
题目描述
给你一个二叉树的根节点 root
,树中每个节点都存放有一个 0
到 9
之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
- 例如,从根节点到叶节点的路径
1 -> 2 -> 3
表示数字123
。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
2
3
4
5
6
示例 2:
输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026
2
3
4
5
6
7
思路1: 递归
我们从根节点出发,每向下一层,就将当前路径值更新为 当前值 * 10 + 当前节点的值
,直到叶子节点为止,将该值加入总和。
var sumNumbers = function(root) {
const dfs = (node, currSum) => {
if (!node) return 0;
let sum = currSum * 10 + node.val;
// 如果是叶子节点
if (!node.left && !node.right) {
return sum;
}
return dfs(node.left, sum) + dfs(node.right, sum);
};
return dfs(root, 0);
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
时间复杂度:O(n)
空间复杂度:O(h)
bfs:层序遍历
我们在队列中同时存储:
- 当前节点
node
- 从根到当前节点构成的数字
num
当我们遇到叶子节点时,把这个 num
加入结果即可。
var sumNumbers = function(root) {
if (!root) return 0;
let sum = 0;
let queue = [[root, root.val]];
while (queue.length > 0) {
let [node, currNum] = queue.shift();
// 如果是叶子节点,加到总和里
if (!node.left && !node.right) {
sum += currNum;
}
// 加入左右子节点,并更新路径数值
if (node.left) {
queue.push([node.left, currNum * 10 + node.left.val]);
}
if (node.right) {
queue.push([node.right, currNum * 10 + node.right.val]);
}
}
return sum;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
时间复杂度:O(n)
空间复杂度:O(n)
# lc208. 实现 Trie (前缀树)中等hot
题目描述
Trie (opens new window)(发音类似 "try
")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie
类:
Trie()
初始化前缀树对象。void insert(String word)
向前缀树中插入字符串word
。boolean search(String word)
如果字符串word
在前缀树中,返回true
(即,在检索之前已经插入);否则,返回false
。boolean startsWith(String prefix)
如果之前已经插入的字符串word
的前缀之一为prefix
,返回true
;否则,返回false
。
示例:
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
2
3
4
5
6
7
8
9
10
11
12
13
14
思路
对插入进行讲解一下
insert
之后是这样,最里面有一个end
属性,searchPrefix
也是一层一层的找
class TrieNode {
children: Map<string, TrieNode>;
isEnd: boolean;
constructor() {
this.children = new Map();
this.isEnd = false;
}
}
class Trie {
root: TrieNode;
constructor() {
this.root = new TrieNode();
}
insert(word: string): void {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, new TrieNode());
}
node = node.children.get(ch)!;
}
node.isEnd = true;
}
search(word: string): boolean {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch)!;
}
return node.isEnd;
}
startsWith(prefix: string): boolean {
let node = this.root;
for (const ch of prefix) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch)!;
}
return true;
}
}
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
36
37
38
39
40
41
42
43
44
45
46