小宋爱睡觉 小宋爱睡觉
首页
  • HTML
  • CSS
  • JavaScript
  • Vue
  • React
  • 计算机网络
  • 浏览器原理
  • 性能优化
  • 设计模式
手写系列
  • 字符串
  • 数组
  • 链表
  • 树
  • 动态规划
  • 排序算法
  • GitHub (opens new window)
  • JueJin (opens new window)
首页
  • HTML
  • CSS
  • JavaScript
  • Vue
  • React
  • 计算机网络
  • 浏览器原理
  • 性能优化
  • 设计模式
手写系列
  • 字符串
  • 数组
  • 链表
  • 树
  • 动态规划
  • 排序算法
  • GitHub (opens new window)
  • JueJin (opens new window)
  • 二叉树的遍历
    • lc144. 二叉树的前序遍历
    • lc589. N叉树的前序遍历
    • lc102. 二叉树的层序遍历
    • lc103. 二叉树的锯齿形层序遍历
    • lc958. 二叉树的完全性检验
    • lc114. 二叉树的展开为链表
    • 129. 求根节点到叶节点数字之和
    • lc208. 实现 Trie (前缀树)
  • 二叉树的广度优先
  • 二叉树的深度优先
  • 二叉树的递归
  • 二叉搜索树
  • 树
Crucials
2021-12-23

二叉树的遍历

# 二叉树的遍历

# lc144. 二叉树的前序遍历简单 hot

题目描述

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

img

输入:root = [1,null,2,3]
输出:[1,2,3]
1
2

示例 2:

输入:root = []
输出:[]
1
2

示例 3:

输入:root = [1]
输出:[1]
1
2

示例 4:

img

输入:root = [1,2]
输出:[1,2]
1
2

示例 5:

img

输入:root = [1,null,2]
输出:[1,2]
1
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
};
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

法二:迭代

用栈来模拟递归

  • 维护一个栈数组和一个结果数组

  • 首先根节点入栈

  • 由于栈是后进先出

  • 首先根节点出栈,将根节点的值放在结果数组中

  • 如果该根节点存在右节点,让右节点入栈

  • 接着如果该根节点存在左节点,左节点入栈

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;
};
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
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:

img
输入:root = [1,null,3,2,4,null,5,6]

输出:[1,3,5,6,2,4]
1
2
3

示例 2:

img
输入: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]
1
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
};
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
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
1
2
3
4
5
6

返回其层序遍历结果:

[
  [3],
  [9,20],
  [15,7]
]
1
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;
};
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

时间复杂度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
};
1
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
1
2
3
4
5
6
7

返回锯齿形层序遍历如下:

[
  [3],
  [20,9],
  [15,7]
]
1
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
};
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

时间复杂度O(n)

空间复杂度O(n)

# lc958. 二叉树的完全性检验中等hot

题目描述

给定一个二叉树,确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

示例 1:

img

输入:[1,2,3,4,5,6]

输出:true

解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),且最后一层中的所有结点({4,5,6})都尽可能地向左。
1
2
3
4
5

示例 2:

输入:[1,2,3,4,5,null,7]

输出:false

解释:值为 7 的结点没有尽可能靠向左侧。
1
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;
};
1
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:

img
输入:root = [1,2,5,3,4,null,6]

输出:[1,null,2,null,3,null,4,null,5,null,6]
1
2
3

示例 2:

输入:root = []

输出:[]
1
2
3

示例 3:

输入:root = [0]

输出:[0]
1
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]
  }
};
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;
  }
}
1
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:

img

输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
1
2
3
4
5
6

示例 2:

img

输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026
1
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);
};

1
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;
};
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

时间复杂度: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
1
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;
  }
}
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
36
37
38
39
40
41
42
43
44
45
46
上次更新: 2025/06/04, 10:21:03
二叉树的广度优先

二叉树的广度优先→

Copyright © 2021-2025 粤ICP备2021165371号
  • 跟随系统
  • 浅色模式
  • 深色模式