二叉树

发表于2024-07-19更新于2024-07-23

二叉树

二叉树分类

二叉树遍历

  • 前序:根左右
  • 中序:左根右
  • 后序:左右根

递归法

递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
前序方法1
var preorderTraversal = function(root) {
  let res = []
  const dfs = ()=>{
    if (root === null) return
    res.push(root.val)
    dfs(root.left)
    dfs(root.right)
  }
  //调用
  dfs(root)
  return res
};
前序方法2:
var preorderTraversal = function (root) {
  return root
    ? [
        root.val,
        ...preorderTraversal(root.left),
        ...preorderTraversal(root.right)
      ]
    : []
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
中序方法1:
var inorderTraversal = function(root) {
  let res=[]
  const dfs = (r)=>{
    if (r===null) return
    dfs(r.left)
    res.push(r.val)
    dfs(r.right)
  }
  dfs(root)
  return res
};
中序方法2:
var inorderTraversal = function (root) {
  return root
    ? [
        ...inorderTraversal(root.left),
        root.val,
        ...inorderTraversal(root.right)
      ]
    : []
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
后序方法1
var postorderTraversal = function(root) {
  let res = []
  const dfs = (r)=>{
    if (r===null) return
    dfs(r.left)
    dfs(r.right)
    res.push(r.val)
  }
  dfs(root)
  return res
};
后序方法2
var postorderTraversal = function (root) {
  return root
    ? [
        ...postorderTraversal(root.left),
        ...postorderTraversal(root.right),
        root.val
      ]
    : []
}

迭代法–栈

图 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
前序
// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
var preorderTraversal = function (root) {
  let res = []
  if (!root) return res
  let queue = [root]
  while(queue.length){
    cur = queue.pop()
    res.push(cur.val)
    cur.right && queue.push(cur.right)
    cur.left && queue.push(cur.left)
  }
  return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转
后序
var postorderTraversal = function (root) {
  let res = []
  if (!root) return res
  let stack = [root]
  while(stack.length){
    cur = stack.pop()
    res.push(cur.val)
    cur.left && stack.push(cur.left)
    cur.right && stack.push(cur.right)
  }
  return res.reverse()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
中序
var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  if (!root) return res
  const stack = []
  cur = root
  while (cur || stack.length){
    if (cur){
      stack.push(cur)
      cur = cur.left
    }
    else{
      cur = stack.pop()
      res.push(cur.val)
      cur = cur.right
    }
  }
  return res
}

观察上述代码发现,前后序可以通过调整代码顺序,实现.但中序却喝前后序的方法不同,那有没有统一的迭代方法呢?

我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！ (opens new window)中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  const stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    if (!node) {
      res.push(stack.pop().val)
      continue
    }
    if (node.right) stack.push(node.right) // 右
    stack.push(node) // 中
    stack.push(null)
    if (node.left) stack.push(node.left) // 左
  }
  return res
}