跳到主要内容

树

树的遍历​

通常使用栈来储存遍历的结果

遍历复杂度为 O(n) 空间复杂度, 如果用栈来储存, 那么最糟糕情况下(树是线性的), 复杂度为 O(n)

前序遍历​

根->左->右

使用栈来遍历, 右子树先进栈, 左子树后进栈

时间复杂度: O(n) 空间复杂度: O(w)

中序遍历​

左->根->右

时间复杂度: O(n) 空间复杂度: O()

后序遍历​

左->右->根

层序遍历 (BFS) 广度优先搜索​

使用队列来做, 入栈顺序为: 左->右

深度优先搜索 (DFS)​

使用栈来实现, 入栈顺序为: 右->左

常见题​

  • 判断两个二叉树是否相等: 100*相同的数
    • 递归做法
    • 两个栈的做法, 栈用来先序遍历树, 遍历的过程中进行比较
  • 判断二叉树是否对称: 101*对称二叉树
    • 递归 ￿ 做法
    • 栈做法, 每次 pop 两个节点出来比较, 入栈方式是重点
  • 求树的最大深度
    • 递归法
    • 队列层序遍历, 然后求深度

求树的高度​

树的高度需要使用后序遍历, 每回归一层需要用 max(left, right) + 1 当做当前层的高度

function height($root) {
    if ($root === null) {
        return -1;
    }
    return 1 + max(height($root->left), height($root->right));
}

二叉搜索树特性​

若左子树不为空, 则左子树上的节点均小于根节点, 若右子树不为空, 则右子树上的节点均大于根节点. 左右子树也均为二叉排序树.