扩展
- 多叉树的遍历，参考图的遍历
- O(1)空间的遍历，Morris Traversal
- 首先打印
root - 然后遍历左子树的所有节点
- 再遍历右子树的所有节点
在遍历顺序中，根节点是在最前面的，所以叫做前序遍历。
print(root)
preorder(root.left)
preorder(root.right)
- 时间复杂度：O(2^h)，h 为二叉树的高度。也可以表示为 O(n)，n 为二叉树的节点数。
- 空间复杂度：O(h)，h 为二叉树的高度。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root, res = []) {
if (!root) return []
res.push(root.val)
root.left && preorderTraversal(root.left, res)
root.right && preorderTraversal(root.right, res)
return res
}- 使用一个栈来实现 DFS，首先把 root 入栈，
- 当栈不为空时，弹出栈顶元素 node，然后把 node 的左右节点分别入栈，接着把 node 的值存到结果数组 res，
- 当栈为空时遍历结束。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
const stack = [root]
const res = []
while (stack.length > 0) {
const node = stack.pop()
if (node) {
res.push(node.val)
stack.push(node.right, node.left)
}
}
return res
}- 首先遍历左子树的所有节点
- 打印
root - 再遍历右子树的所有节点
在遍历顺序中，根节点是在中间的，所以叫做中序遍历。
inorder(root.left)
print(root)
inorder(root.right)
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root, res = []) {
if (!root) return []
root.left && inorderTraversal(root.left, res)
res.push(root.val)
root.right && inorderTraversal(root.right, res)
return res
}- 二叉树的中序遍历是 left -> root -> right
- 我们从 root 开始遍历，把 root 入栈，然后 root.left 入栈，然后 root.left.left 入栈，...，直到遍历到最深层的叶子左节点
- 开始将栈顶元素弹出，如果该元素没有右子节点，说明这是个左子节点，直接放入 res 数组，
- 如果该元素有右子节点，说明这还是这个父节点，把父节点放入 res 数组，然后把它的右子节点当成新的 root 重复步骤 2-4。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
const stack = []
const res = []
while (root || stack.length > 0) {
while (root) {
stack.push(root)
root = root.left
}
root = stack.pop()
res.push(root.val)
root = root.right
}
return res
}- 首先遍历左子树的所有节点
- 然后遍历右子树的所有节点
- 最后打印
root
在遍历顺序中，根节点是在最后面的，所以叫做后序遍历。
postorder(root.left)
postorder(root.right)
print(root)
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root, res = []) {
if (!root) return []
root.left && postorderTraversal(root.left, res)
root.right && postorderTraversal(root.right, res)
res.push(root.val)
return res
}- 二叉树的前序遍历是 root -> left -> right
- 二叉树的后序遍历是 left -> right -> root
- 可以看到后序遍历差不多是前序遍历的结果倒转过来，我们可以把前序遍历的套路拿过来稍做改动。
- 只需把第 2 步把 node 存入 res 这一步由
res.push(node.val)改为res.unshift(node.val)，并且将左右子节点入栈的顺序调换一下即可。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
const stack = [root]
const res = []
while (stack.length > 0) {
const node = stack.pop()
if (node) {
stack.push(node.left, node.right)
res.unshift(node.val)
}
}
return res
}- 可以利用一个队列来简化遍历操作，首先将根节点入列；
- 接着开始出列，再分别把出列节点的左右子节点入列，重复这一步的操作直到所有节点都被遍历了；
- 问题是，如何识别当前行是否已经遍历完成？我们可以使用一个特殊标识符(比如
null)； - 在将根节点入列后，马上入列一个
null作为第一行的结束标识； - 接着根节点出列，根节点的左右子节点入列；接着
null出列，说明第一行已经遍历结束，这时候队列里的都是第二行的节点，此时我们再入列一个null作为第二行的结束标识，再次开始出列，重复这个操作直到队列为空； - 注意，我们入列
null的时候要先判断队列当前是否为空，如果队列为空就不要入列了，不然会无限循环的。
关键点
- 用一个特殊标识符
null来表示每一行的末尾； - 如果不想使用特殊标识符，可以在遍历每一行之前记录队列当前的长度，参考下方的 Python Code。
- 时间复杂度：O(n)，n 为树的节点数。
- 空间复杂度：O(2^h)，h 为树的高度，队列的最大长度是最深一层叶子节点的总数 2^(h-1)。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
if (!root) return []
const result = []
const queue = [root, null]
let level = 0
while (queue.length > 0) {
const node = queue.shift()
if (node) {
result[level] || (result[level] = [])
result[level].push(node.val)
node.left && queue.push(node.left)
node.right && queue.push(node.right)
} else {
queue.length > 0 && queue.push(null)
level++
}
}
return result
}Python Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None: return []
items = []
queue = [root]
level = []
while len(queue) > 0:
size = len(queue)
level = []
for i in range(size):
node = queue.pop(0)
if node != None:
level.append(node.val)
if node.left != None: queue.append(node.left)
if node.right != None: queue.append(node.right)
items.append(level)
return items多加一个变量来标识当前遍历的深度。
- 时间复杂度：O(n), n 为二叉树的节点数。
- 空间复杂度：O(n), n 为二叉树的节点数，
res数组的空间是 O(n)，调用栈的空间最大是 O(h)，h 是二叉树的深度，因为 n >= h，所以最后还是 O(n)。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root, depth = 0, res = []) {
if (!root) return []
res[depth] || (res[depth] = [])
res[depth].push(root.val)
levelOrder(root.left, depth + 1, res)
levelOrder(root.right, depth + 1, res)
return res
}