深度优先遍历 DFS
解题思路
确定递归函数的参数和返回值；
确定终止条件；
确定单层递归的逻辑；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
代码实现
var inorderTraversal = function (root) {
const res = [];
preorder(root, res);
return res;
};
const preorder = (root, res) => {
// 当前结点为空时，无需进行递归
if (!root) return;
preorder(root.left, res); // 前序遍历左子树
res.push(root.val); // 记录根节点值
preorder(root.right, res); // 前序遍历右子树
}
广度优先遍历 BFS
解题思路
中序遍历也叫 中根遍历 ，则遍历顺序为 左 -> 根 -> 右；
非递归的遍历时，算法需要借助一个栈 stk 来存储根节点，利用根节点找到相应的右节点；
- 首先访问根节点，如果此节点的左子树不为空，将此根节点入栈 res 中，一直查找左节点直到节点的左子树为空时；
- 从堆栈 stk 中弹出一个根节点，利用根节点找到右节点，再按照相同的方法访问节点；
- 如此反复，直到堆栈为空时结束；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
代码实现
var inorderTraversal = (root) => {
const res = [];
const stk = [];
while (root || stk.length > 0) {
// 1. 一直向左查找，找到最左边的节点
while (root) {
stk.push(root);
root = root.left;
}
// 2. 出栈栈顶节点
root = stk.pop();
res.push(root.val);
// 3. 利用栈顶节点，去寻找右孩子节点
root = root.right;
}
return res;
};
Morris 遍历
解题思路
如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即
x = x.right；如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点）记为 predecessor ，根据 predecessor 的右孩子是否为空，进行如下操作：
- 如果 predecessor 的右孩子为空，则将其右孩子指向 x ，然后访问 x 的左孩子，即
x = x.left；- 如果 predecessor 的右孩子不为空，则此时其右孩子指向 x ，说明已经遍历完 x 的左子树，这时将 predecessor 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即
x = x.right；
- 重复上述操作，直至访问完整棵树；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉搜索树的节点个数，Morris 遍历中每个节点会被访问两次，因此总时间复杂度为O(2n) => O(n) -
空间复杂度：
O(1)
代码实现
var inorderTraversal = function (root) {
const res = [];
let predecessor = null;
while (root) {
if (root.left) {
// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
predecessor = root.left;
while (predecessor.right && predecessor.right !== root) {
predecessor = predecessor.right;
}
// 让 predecessor 的右指针指向 root，继续遍历左子树
if (!predecessor.right) {
predecessor.right = root;
root = root.left;
}
// 说明左子树已经访问完了，我们需要断开链接
else {
res.push(root.val);
predecessor.right = null;
root = root.right;
}
}
// 如果没有左孩子，则直接访问右孩子
else {
res.push(root.val);
root = root.right;
}
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 144. 二叉树的前序遍历
上一篇
评论
