树
树的遍历
通常使用栈来储存遍历的结果
遍历复杂度为 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));
}
二叉搜索树特性
若左子树不为空, 则左子树上的节点均小于根节点, 若右子树不为空, 则右子树上的节点均大于根节点. 左右子树也均为二叉排序树.