二叉树节点的定义

1
2
3
4
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

先序遍历

根节点 -> 左子树 -> 右子树

递归

1
2
3
4
5
6
7
8
function preOrder(root, result = []) {
    if (!root) return result;
    const { left, right, val } = root;
    result.push(val);
    left && preOrder(left, result);
    right && preOrder(right, result);
    return result;
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
function preOrder(root) {
    const result = [];
    if (!root) return result;
    const stack = [root];
    while (stack.length) {
        const { left, right, val } = stack.pop();
        result.push(val);
        right && stack.push(right);
        left && stack.push(left);
    }
    return result;
}

中序遍历

左子树 -> 根节点 -> 右子树

递归

1
2
3
4
5
6
7
8
function inOrder(root, result = []) {
    if (!root) return result;
    const { left, right, val } = root;
    left && inOrder(left, result);
    result.push(val);
    right && inOrder(right, result);
    return result;
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function inOrder(root) {
    const result = [];
    if (!root) return result;
    const stack = [];
    while (root || stack.length) {
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        result.push(root.val);
        root = root.right;
    }
    return result;
}

后序遍历

左子树 -> 右子树 -> 根节点

递归

1
2
3
4
5
6
7
8
function postOrder(root, result = []) {
    if (!root) return result;
    const { left, right, val } = root;
    left && postOrder(left, result);
    right && postOrder(right, result);
    result.push(val);
    return result;
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
function postOrder(root) {
    const result = [];
    if (!root) return result;
    const stack = [root];
    while (stack.length) {
        const { left, right, val } = stack.pop();
        result.unshift(val);
        left && stack.push(left);
        right && stack.push(right);
    }
    return result;
};