是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有 N 个节点和 N-1 条边的一个有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。

概念

  • 前序遍历:前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树
  • 中序遍历:中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树
  • 后序遍历:后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点
  • 递归和迭代

所谓前、中、后,不过是根的顺序,即也可以称为先根遍历、中根遍历、后根遍历

举个例子:

前序遍历为:F B A D C E G I H
中序遍历为:A B C D E F G H I
后序遍历为:A C E D B H I G F

二叉树的前序遍历

递归解法

思路:根据根、左、右的顺序遍历即可

/**
 * 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 preorderTraversal = root => {
    return root ? [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)] : []
    }

迭代解法

思路:利用栈来记录遍历的过程,实际上,递归就使用了调用栈,所以这里我们可以使用栈来模拟递归的过程

  • 首先根入栈
  • 将根节点出栈,将根节点值放入结果数组中
  • 然后遍历左子树、右子树,因为栈是先入后出,所以,我们先右子树入栈,然后左子树入栈
  • 继续出栈(左子树被出栈)…….
  • 依次循环出栈遍历入栈,直到栈为空,遍历完成
/**
 * 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 preorderTraversal = function(root) {
    const list = []
    const stack = []

    root &&  stack.push(root)
    while(stack.length > 0) {
        const popNode = stack.pop()
        list.push(popNode.val)

        popNode.right && stack.push(popNode.right)
        popNode.left && stack.push(popNode.left)
    }
    return list
};

二叉树的中序遍历

递归解法

思路:左-跟-右

var inorderTraversal = root => {
    return root ? [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)] : []
}

迭代解法

思路:

  • 首先按从上到下的顺序左子树入栈,则栈的最顶层为最小的左孩子
  • 取顶层的值,加入数组
  • 取跟(上一层)加入数组
  • 取右孩子加入数组

这里比较明显的感觉到了DFS的思想

var inorderTraversal = root => {
    let list = [], stack = []
    while(root || stack.length) {
        while(root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        list.push(root.val)
        root = root.right    
    }
    return list
}

[二叉树的后序遍历]()