二叉树节点的定义

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;
};