树

想普及一下树的知识，个人认为树是算法必须要牢牢掌握的一部分。

一般树的逻辑可以说是灰常滴简单了：

除根节点之外的每个节点只有一个父节点，根节点没有父节点。
除叶节点之外所有节点都有一个或多个子节点，叶节点没有子节点。

父节点和子节点之间是用指针连接，所以树会涉及到大量的指针，因此与树有关的面试题都不太容易，但是越不容易的知识点，我们就越要攻克。

树的遍历

但是面试时候提到的树，大部分都是二叉树。二叉树是树的一种特殊结构，在二叉树中每个节点最多只能有两个子节点。在二叉树中最重要的考点莫过于树的遍历，即按照某一个顺序遍历访问树中的所有节点。

二叉树的遍历可以有以下几种：

前序遍历

前序遍历：先访问根节点，再访问左节点，最后访问右节点

// 递归版本
const preOrderTraverse = (root) => {
    let list = []

    const preOrder = (node) => {
        if(node !== null) {
            // 先访问根节点
            list.push(node.val)
            // 再访问左节点
            preOrder(node.left)
            // 最后访问右节点
            preOrder(node.right)
        }
    }
    inOrder(root)

    return list
}

// 非递归版本
const preOrderTraverseUnRecur = (root) => {
    let list = [];
    let stack = [root];

    while(stack.length !== 0) {
        const curNode = stack.pop()

        const left = curNode.left
        const right = curNode.right

        // 第一步的时候，先访问的是根节点
        list.push(curNode.val)

        if(right) {
            stack.push(right)
        }

        // 因为pop是取出最后一个元素，所以我们要确保首先拿到的是左节点
        if(left) {
            stack.push(left)
        }
    }
}

中序遍历

中序遍历：先访问左节点，再访问中节点，最后访问右节点

// 递归版本
const inOrderTraverse = (root) => {
    let list = []

    const inOrder = (node) => {
        if(node !== null) {
            inOrder(node.left)
            list.push(node.val)
            inOrder(node.right)
        }
    }

    inOrder(root)

    return list
}

// 非递归版本
const inOrderTraverseUnRecur = (root) => {
    let list = []
    // 借助了栈，先进后出的概念
    let stack = []
    let head = root

    while(stack.length !== 0 || head !== undefined) {
        while(head !== undefined) {
            stack.push(head)
            head = head.left
        }

        if(stack.length !== 0) {
            head = stack.pop()
            list.push(head.val)
            head = head.right
        }
    }

    return list
}

后序遍历

后序遍历：先访问左节点，再访问右节点，最后访问根节点

// 递归
const postOrderTraverse = (root) => {
    let list = []

    const postOrder = (node) => {
        if(!node) {
            postOrder(node.left)
            postOrder(node.right)
            list.push(node.val)
        }
    }

    postOrder(root)

    return list
}

// 非递归
const postOrderTraverseUnRecur = (root) => {
    let list = []
    if(root !== undefined) {
        let s1 = []
        let s2 = []

        s1.push(root)

        while(s1.length !== 0) {
            head = s1.pop()
            s2.push(head)

            if(head.left !== undefined) {
                s1.push(head.left)
            }

            if(head.right !== undefined) {
                s1.push(head.right)
            }
        }

        while(s2.length !== 0) {
            var item = s2.pop()
            list.push(item.val)
        }
    }

    return list
}

为了方便记忆，可以这样记：前序遍历对应的前是根节点最先访问。中序遍历对应的前是根节点放在中间访问。后序遍历对应的前是根节点最后才访问。

这三种遍历方式都有 递归 和 循环 两种不同的实现方式，但是面试官更喜欢考我们的是循环实现方式，所以我们应该要掌握这三种遍历的六种遍历方式!

广度优先遍历

广度优先遍历：即先访问树的第一层节点，接着访问第二层节点…一直访问到最后一层节点

深度优先遍历

深度优先遍历：即先访问树的根节点，再访问根节点的子节点，先往深层访问，深层访问节点结束了，再返回访问同层节点，之后再继续往深层访问节点…

二叉搜索树

二叉搜索树：左子节点总是小于或等于根节点，而右节点总是大于或等于根节点。可以在 O(logn) 内根据数值在二叉搜索树中找到一个节点

堆

堆：分为最大堆和最小堆。最大堆中根节点的值最大，在最小堆中根节点的值最小。需要快速找到最大值或最小值都可以用堆来解决

红黑树

红黑树：把树中的节点定义为红，黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍

# 二叉树, 树

树