30、二叉树的先中后序遍历（递归版）

二叉树概念

• 树中每个节点最多只能有两个子节点
• 在JavaScript中通常用Object来模拟二叉树

  const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: null
    },
    right: {
        val: 3,
        left: null,
        right: null
    }
  }

先序遍历（中左右）

• 访问根节点
• 对根节点的左子树进行先序遍历
• 对根节点的右子树进行先序遍历

const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        },
        right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null
        },
        right: {
            val: 7,
            left: null,
            right: null
        }
    }
}

const preoder = root => {
    /** 若根节点为空 */
    if (!root) return
    console.log(root.val)
    preoder(root.left)
    preoder(root.right)
}
preoder(binaryTree)

输出结果为
1
2
4
5
3
6
7

中序遍历（左中右）

• 对根节点的左子树进行中序遍历
• 访问根节点
• 对根节点的右子树进行中序遍历

const inorder = root => {
    /** 若根节点为空 */
    if (!root) return
    inorder(root.left)
    console.log(root.val);
    inorder(root.right)
}

inorder(binaryTree)

输出结果为
4
2
5
1
6
3
7

后序遍历（左右中）

• 对根节点的左子树进行后序遍历
• 对根节点的右子树进行后续遍历
• 访问根节点 ```javascript const postorder = root => { /* 若根节点为空 / if (!root) return postorder(root.left) postorder(root.right) console.log(root.val); }

postorder(binaryTree) ``` 输出结果为
4
5
2
6
7
3
1