数据结构 | 二叉树

树有几个概念：

• 拥有相同父节点的节点，互称为兄弟节点
• 节点的深度 ：从根节点到该节点所经历的边的个数
• 节点的高度 ：节点到叶节点的最长路径
• 树的高度：根节点的高度

B、C、D就互称为兄弟节点，其中，节点B的高度为2，节点B的深度为 1，树的高度为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)
 * }
 */

// 递归先序遍历： 根 - 左 - 右
var preorderTraversal = (root) => {
    let result = []
    var preOrderTraverseNode = (node) => {//递归函数
        if(node){
            result.push(node);
            preOrderTraverseNode(node.left);
            preOrderTraverseNode(node.right);
        }
    }
    preOrderTraverseNode(root)
    return result
};


// 递归中序遍历： 左根右
var inorderTraversal = (root) => {
    let result = []
    var inorderTraverseNode = (node) => {//递归函数
        if (node) {

            inorderTraverseNode(node.left);
            result.push(node);
            inorderTraverseNode(node.right);
        }
    }
    inorderTraverseNode(root)
    return result
};


// 递归后序遍历： 左右根
var inorderTraversal = (root) => {
    let result = []
    var postorderTraversal = (node) => {//递归函数
        if (node) {

            postorderTraversal(node.left);
            
            postorderTraversal(node.right);
            result.push(node);
        }
    }
    postorderTraversal(root)
    return result
};

非递归版：

先序遍历：

• 首先根入栈
• 将根节点出栈，将根节点值放入结果数组中
• 然后遍历左子树、右子树，因为栈是先入后出，所以，我们先右子树入栈，然后左子树入栈
• 继续出栈（左子树被出栈）…….继续将左子树的右节点入栈，将左子树左节点入栈再出栈....循环

每pop完添加右左节点直接输出(访问)即可完成前序非递归遍历。

// 前序遍历
const preorderTraversal = (root) => {
    const list = [];
    const stack = [];
    
    // 当根节点不为空的时候，将根节点入栈
    if(root) stack.push(root)
    while(stack.length > 0) {
        const curNode = stack.pop()
        // 第一步的时候，先访问的是根节点
        list.push(curNode.val)
        
        // 我们先打印左子树，然后右子树
        // 所以先加入栈的是右子树，然后左子树
        if(curNode.right !== null) {
            stack.push(curNode.right)
        }
        if(curNode.left !== null) {
            stack.push(curNode.left)
        }
    }
    return list
}

层次遍历（非递归版）

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorder = function(root) {
    if(!root) return [];
    let stack=[];
    let p=root;
    stack.push(root);
    let res=[];
    while(stack.length>0){
        let curnode=stack.pop();
        res.push(curnode.val);
        for(let i=curnode.children.length-1;i>=0;i--){
            stack.push(curnode.children[i]);
        }
    }
    return res;
};

中序遍历：

中序排列的顺序是：左节点，根节点，右节点。那么我们在经过根节点的前面节点 不能释放， 因为后面还需要用到它。所以要用栈先储存。 它的规则大致为：

• 栈依次存入左节点所有点，直到最左侧在栈顶。
• 开始抛出栈顶并访问。(例如第一个抛出2)。如果有右节点。那么将右节点加入栈中，然后右节点一致左下遍历直到尾部。（这里5和7没有左节点，所以不加）但是如果抛出15。右节点加入23.再找23的左侧节点加入栈顶。就这样循环下去直到栈为空。

// 中序遍历
const inorderTraversal = (root) => {
    if(!root) return[];
    const list=[];
    const stack = [];
    while(stack.length>0 || p){
        while(p){//先把所有左节点压入栈，然后每个左节点通过左、中、右遍历
            stack.push(p);
            p=p.left;//遍历到最后p为null
        }
        const curNode=stack.pop();//第一个访问最底层的左节点,通过出栈来访问左父节点
        list.push(curNode.val);
        p=curNode.right;//如果右节点不为空，下一层循环中遍历它的左子树....
    }
    return list;
    

}

后序遍历

在前面的前序和中序先到最左侧压入栈的时候，两种顺序依次是

• 前序: 中入栈（根节点）——>中出栈——>右入栈——>左入栈——>左出栈——>出栈节点的右孩子入栈——>左孩子入栈.....循环
• 在入栈时候操作即可前序
• 中序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈 ——>右孩子入出——>右出栈 按照出栈顺序即可完成中序

用unshift实现

const postorderTraversal = root => {
    if (!root) return [];
    const arr = [root];
    const res = [];
    while (arr.length) {
        const n = arr.pop();
        res.unshift(n.val);
        n.left && arr.push(n.left);
        n.right && arr.push(n.right);
    }
    return res;
};