1. 树

1.1. 树的遍历

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

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

根->左->右

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

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

左->根->右

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

左->右->根

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

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

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

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

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