算法之二叉树的3种遍历 - 翁先森的博客

一. 前序遍历（中左右）#

144.二叉树前序遍历

1. 递归实现#

按照中间节点先遍历，在遍历左右节点

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[]}
12
 */
13

14

15
var preorderTraversal = function (root) {
16
    let number = [];
17
    getNode(root, number);
18
    return number;
19
};
20

21
const getNode = (node, number) => {
22
    if (node) {
23
        number.push(node.val);
24
        if (node.left) {
25
            getNode(node.left, number)
26
        }
27
        if (node.right) {
28
            getNode(node.right, number);
29
        }
30
    }
31
}

2. 迭代实现#

以显示栈的方式模仿递归。

初始化栈，并将根节点入栈；
当栈不为空时：
- 弹出栈顶元素 n，并将值添加到结果中
- 如果 n 的右节点存在，入栈
- 如果 n 的左节点存在，入栈

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[]}
12
 */
13

14

15
var preorderTraversal = function (root) {
16
    let number = [];
17
    let stack = [root];
18
    while (stack.length) {
19
        const current = stack.shift();
20
        if(current){
21
            number.push(current.val);
22
            if(current.right){
23
                stack.unshift(current.right)
24
            }
25
            if(current.left){
26
                stack.unshift(current.left);
27
            }
28
        }
29
    }
30

31
    return number;
32
};

二. 中序遍历（左中右）#

1. 递归实现#

先左节点，然后中间节点，之后右节点

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[]}
12
 */
13
var inorderTraversal = function (root) {
14
    const number = [];
15
    getNode(root, number);
16
    return number
17
};
18

19
const getNode = (node, number) => {
20
    if (node && node.left) {
21
        getNode(node.left, number)
22
    }
23
    node && number.push(node.val);
24
    if (node && node.right) {
25
        getNode(node.right, number)
26
    }
27
}

2. 迭代实现#

原理：

代码一：

1
const inorderTraversal = (root) => {
2
  const res = [];
3
  const stack = [];
4

5
  while (root) {        // 能压入栈的左子节点都压进来
6
    stack.push(root);
7
    root = root.left;
8
  }
9
  while (stack.length) {
10
    let node = stack.pop(); // 栈顶的节点出栈
11
    res.push(node.val);     // 在压入右子树之前，处理它的数值部分（因为中序遍历）
12
    node = node.right;      // 获取它的右子树
13
    while (node) {          // 右子树存在，执行while循环
14
      stack.push(node);     // 压入当前root
15
      node = node.left;     // 不断压入左子节点
16
    }
17
  }
18
  return res;
19
};

代码二：

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[]}
12
 */
13
var inorderTraversal = function (root) {
14
    const number = [];
15
    let stack = [];
16
    let tempNode = root;
17
    while(tempNode || stack.length){
18
        if(tempNode){
19
            stack.unshift(tempNode);
20
            tempNode = tempNode.left;
21
        }else{
22
            tempNode = stack.shift();
23
            number.push(tempNode.val);
24
            tempNode = tempNode.right
25
        }
26
    }
27
    return number;
28
};

三. 后序遍历#

1. 递归方式#

左右中

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[]}
12
 */
13
var postorderTraversal = function(root) {
14
    let number = [];
15
    getNode(root,number);
16
    return number;
17
};
18

19
const getNode = (node, number)=>{
20
    if(node && node.left){
21
        getNode(node.left, number);
22
    }
23
    if(node && node.right){
24
        getNode(node.right, number)
25
    }
26
    node && number.push(node.val);
27
}

2. 迭代方式#

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[]}
12
 */
13
const postorderTraversal = (root) => {
14
    const res = [];
15
    const stack = [root];
16

17
    while(stack.length > 0) {
18
        const node = stack.pop()
19
        node && res.unshift(node.val)
20
        if(node?.left) {
21
            stack.push(node.left)
22
        }
23
        if(node?.right) {
24
            stack.push(node.right)
25
        }
26
    }
27
    return res
28
}