二叉树的遍历

Scroll Down

初级数据结构,大佬可以忽略滴~

二叉树的前中后序

很长一段时间我都是通过死记硬背的方法来记二叉树的 前、中、后 序遍历的,但是久了不用就老是忘,忘了又去翻,效率非常的低下,后面看了有位大佬的博客(忘记是哪一篇了,就直接贴大佬的github主页了),保持先左后右的循序,前中后实际上就是指根背遍历到的位置,也就是说:

  1. 前序遍历是指根在前:根 -> 左 -> 右
  2. 中序遍历... 根在中:左 -> 根 -> 右
  3. 后序...根在后:左 -> 右 -> 根

递归法

理解了上面的记忆方法,再来结合递归遍历可以轻松的写出树的前中后遍历。

前序遍历: 先打印出根节点,然后递归左子树,最后递归右子树
/**
 * 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) {
    if(!root) return []
    let arr = []
    const readTree = (tree) => {
        if(!tree) return
        arr.push(tree.val)
        readTree(tree.left)
        readTree(tree.right)
    }
    readTree(root)
    return arr // 最终遍历的结果
};
中序遍历: 先递归左子树,然后打印根节点,最后递归右子树
/**
 * 数据结构同
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    if(!root) return []
    let arr = []
    const readTree = (tree) => {
        if(!tree) return
        readTree(tree.left)
        arr.push(tree.val)
        readTree(tree.right)
    }
    readTree(root)
    return arr // 最终遍历的结果
};
后序遍历: 先递归左子树,然后递归右子树,后打印根节点
/**
 * 数据结构同
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    if(!root) return []
    let arr = []
    const readTree = (tree) => {
        if(!tree) return
        readTree(tree.left)
        readTree(tree.right)
        arr.push(tree.val)
    }
    readTree(root)
    return arr // 最终遍历的结果
};

结合此方法,以后遇到二叉树的遍历,再也不用怕啦~