二叉树遍历（Binary Tree）

简介

二叉树（Binary Tree）：计算机中数据结构的一种，是树形结构的一个重要类型。结构类型是每个节点最多有两个子树的树结构。特点是每个节点最多只能有了两棵子树，且有左右之分。

定义

二叉树是指树中节点的度不大于2的有序树，是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

相关术语

• 叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。
• 节点的关系：节点子树的根节点为该节点的孩子节点。相应该节点称为孩子节点的双亲节点。
• 节点的度：一个节点拥有子树的数目称为节点的度
• 节点的层级：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层
• 数的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度

基本形态

• 空二叉树
• 只有一个跟节点的二叉树
• 只有左子树
• 只有右子树
• 满二叉树

特殊类型

• 满二叉树 ：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。一棵深度为k且有个结点的二叉树称为满二叉树
• 完全二叉树 ：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树

二叉树遍历

例图

• 先序遍历：根节点 –> 左子树 –> 右子树 ==> A 、B 、D 、E 、C 、F 、G
• 中序遍历 ：左子树 –> 根节点 –> 右子树 ==> D、B、E、A 、F 、C、G
• 后序遍历：左子树 –> 右子树 –> 根节点 ==> D、E、B、F、G、C、A
• 层级遍历：也叫层序遍历，按层遍历 ==> A、B、C、D、E、F、G

代码实现

递归实现

//先序遍历
let result = [];
function recursive(res,root){
    if (root == null){
        return [];
    }
    result.push(root.val);
    recursive(result,root.left);
    recursive(result,root.right);
}

//中序遍历
let result = [];
function recursive(result,root){
    if(root == null){
        return [];
    }
    recursive(result,root.left);
    result.push(root.val);
    recursive(result,root.right);
}

//后序遍历
let result = [];
function recursive(result,root){
    if(root == null){
        return [];
    }
    recursive(result,root.left);
    recursive(result,root.right);
    result.push(root.val);
}

非递归实现

非递归实现，其实就是迭代方法，引入栈来替代递归。由于栈的特性是后进先出，所以进栈的时机和递归是相反的 。所以利用递归的思路用栈实现时，需要先放右节点进栈，再放左节点进栈。这样可以保证每次出栈取到的节点都是左节点优先，达到和递归顺序一样的效果。

先序遍历

先序遍历的顺序：根–左–右

所以每次访问

• 常规解法

var preorderTraversal = function(root) {
    if (root == null){
        return [];
    }
    let stack = [];
    let result = [];
    let node = root;
    while(stack.length > 0 || node != null){
        if(node != null){
            result.push(node.val);
            stack.push(node);
            node = node.left;
        }else{
            node = stack.pop();//出栈的同时访问右节点，保证访问顺序是先左后右
            node = node.right;
        }
    }
    return result;
};

• 技巧性解法

//先序遍历
var preorderTraversal = function(root) {
    if (root == null){
        return [];
    }
    let stack = [root];
    let result = [];
    while(stack.length > 0){
        let node = stack.pop();
        // 由于栈先进后出的特性，先 push right，再 push left
        if(node.right != null){
            stack.push(node.right);
        }
        if(node.left != null){
            stack.push(node.left);
        }
        result.push(node.val);
    }
    return result;
};

中序遍历

中序遍历是以 左–根–右 遍历

//中序遍历
var inorderTraversal = function(root) {
    if (root == null){
        return [];
    }
    let stack = [];
    let result = [];
    let node = root;
    while(stack.length > 0 || node != null){
        if(node != null){
            stack.push(node);
            node = node.left;
        }else{
            node = stack.pop();//出栈的同时访问右节点，保证访问顺序是先左后右
            result.push(node.val);
            node = node.right;
        }
    }
    return result;
};

后序遍历

思路：

对于任意节点P而言

1. P如果是叶子节点，直接输出

2. P如果有孩子，且孩子没有被访问过，则按照右孩子，左孩子的顺序依次入栈

3. P如果有孩子，而且孩子都已经访问过，则访问P节点

//后序遍历
var postorderTraversal = function(root) {
    if (root == null){
        return [];
    }
    let stack = [root];
    let result = [];
    let node;
    let preNode = null;
    while(stack.length > 0){
        node = stack[stack.length-1];
        //判断当前节点时，左孩子和右孩子都在根结点前已经被访问
        let visited = preNode != null && (preNode == node.left || preNode == node.right);
        if((node.left == null && node.right == null) || visited){
            result.push(node.val);
            preNode = node;
            stack.pop();
        }else{
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }  
    }
    return result;
};

//后序遍历
var postorderTraversal = function(root) {
    if (root == null){
        return [];
    }
    let result = [];
    let stack = [];
    let node = root;
    while(node != null || stack.length > 0){
        if(node != null){
            stack.push(node);
            result.push(node.val);
            node = node.right;
        }else{
            node = stack.pop();
            node = node.left;
        }
    }
    return result.reverse();  //这里的反转，相当于从栈中取出来节点
};

for(result.length > 0){
  	node = result.pop();
    //打印每个节点的val
}

技巧性解法

var postorderTraversal = function(root) {
    if (root == null){
        return [];
    }
    let result = [];
    let stack = [root];
    
    while(stack.length > 0){
        let node = stack.pop();
        result.push(node.val);
        if(node.left != null){
            stack.push(node.left);
        }
        if(node.right != null){
            stack.push(node.right);
        }
    }
    return result.reverse();
};
//注：后序遍历：左 -- 右 -- 根 
//题中遍历是以 根--右--左出栈的，顺序和后序遍历顺序相反，所以对结果反转得到的就是后序遍历结果

递归和迭代的时间复杂度和空间复杂度都是O(n) ,

区别：在于递归的空间是系统栈维护的

时间复杂度的推导公式：Master公式,Master公式是常用来解决递归问题时间复杂度的通用公式

公式 T(N) = a*T(N / b) + O (N^d)
代入公式得到：T(N)=2T(N/2)+O(1):，其中 a = 2, b = 2, d = 0;
得到 log(2,2) = 1 > 0，代入公式 O(N ^ log(b,a)) = O(N^ log(2,2)) = O(N)

层级遍历（BFS）

//层级遍历
var levelOrderBottom = function(root) {
  	if(root == null){
        return [];
    }
    let result = [];//输出结果
    let queue = [];//队列
    queue.push(root);//进栈
    let node;
    while (queue.length > 0) {
        let count = queue.length;//每个层级下的节点
        let list = [];
        for(let i = 0; i < count; i++){
            node = queue.shift();//出栈
            list.push(node.val);
            if(node.left != null){
                queue.push(node.left);
            }
            if(node.right != null){
                queue.push(node.right);
            }
        }
        result.push(list);//这个如果要求自底向上输出，可以每次添加到首位。result.unshift(list)
    }
    return result;
};

//时间复杂度：每个节点都需要进栈出栈，所以时间复杂度和空间复杂度都是O(n)

二叉树深度 （BFS and DFS）