Skip to main content

二叉树

二叉树

1.二叉树的最大深度

1. DFS（深度优先搜索）

如果我们知道了左子树和右子树的最大深度 ll 和 rr，那么该二叉树的最大深度即为 max(l,r)+1

2. BFS（广度优先搜索）

通用模板

  1. 如果要确定当前遍历到了哪一层，BFS 模板如下。

    这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空：
    let len = queue.length
    while (len) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;
  1. 如果不需要确定当前遍历到了哪一层，BFS 模板如下。
while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)

2.二叉搜索树

中序遍历

中序遍历
var isValidBST = function (root) {
  let stack = []
  let inorder = -Infinity

  while (stack.length || root !== null) {
    while (root !== null) {
      stack.push(root)
      root = root.left
    }
    root = stack.pop()
    // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
    if (root.val <= inorder) {
      return false
    }
    inorder = root.val
    root = root.right
  }
  return true
}