二叉数--前中后层续遍历

二叉树

   我觉得二叉数就是在链表的基础上，增加了带有左右的next结点，也是就是左右子节点，通过左右子节点串联出一颗二叉数。根节点下的左右结点的组成的树，也叫做左右子树。

如何操作二叉树

   对于二叉树的操作无外乎就是遍历二叉树，关于二叉数的遍历有三种:前序遍历、中序遍历、后续遍历，也有叫深度优先遍历、广度优先遍历，对于遍历也主要要两种递归、迭代，二叉树的火数据结构如下：

var node = {
	val : 1 ,
    	left : {   // left 为左子节点
	  xxx  //表示下一个节点
    	},
        right: {// right左子节点
         xxxx //表示下一个节点
        }
  }

leedcode真题

首先最基本的就是如何用递归、迭代来遍历二叉树，从中找出它们的共性：

二叉树的前中后续遍历（leecode144、94、145）

leetcode-cn.com/problems/bi… （二叉树的前序遍历） leetcode-cn.com/problems/bi… （二叉树的中序遍历） leetcode-cn.com/problems/bi… （二叉树的后序遍历）

前中后续遍历思路（递归）

• 当前结点为空结束递归
• 前续：将当前结点加入结果然后依次递归左右子树
• 中续：先递归左子树，左子数递归结束后，将当前结点加入结果，然后递归右子树
• 后续：先依次递归左右子树，左右数递归结束后，将当前结点加入结果。

复杂度分析

时间复杂度：O(n) 空间复杂度：O(n)

//前续遍历
var preorderTraversal = function(root) {
    var res= []
    var dfs = (root) => {
        if(!root) return 
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return res
};
// 中续遍历
var preorderTraversal = function(root) {
    var res= []
    var dfs = (root) => {
        if(!root) return 
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return res
};
//后续遍历
var preorderTraversal = function(root) {
    var res= []
    var dfs = (root) => {
        if(!root) return 
        dfs(root.left)
        dfs(root.right)
        res.push(root.val)
    }
    dfs(root)
    return res
};

前中后续遍历思路（迭代）

• 可以模拟一个栈，细节与递归相同

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

五行代码搞定前中后续遍历

//前续遍历
var preorderTraversal = function(root) {
    var res= []
    var stack = []
    while(root || stack.length) {
        while(root) {
            res.push(root.val) // 前续遍历 首先将值push到结果中
            stack.push(root)  // 根结点入栈，所有左子树依次入栈
            root = root.left	
        }
        root = stack.pop() //出栈 如果没有右结点继续出栈
        root = root.right
    }
    return res
};
//中续遍历
var preorderTraversal = function(root) {
    var res= []
    var stack = []
    while(root || stack.length) {
        while(root) {
            stack.push(root) // 中续遍历 根结点入栈，所有左子树依次入栈
            root = root.left
        }
        root = stack.pop() //出栈
        res.push(root.val) //  将值当前值push到结果中
        root = root.right
    }
    return res
};
//后续遍历
var preorderTraversal = function(root) {
    var res= []
    var stack = []
    while(root || stack.length) {
        while(root) {         
            res.push(root.val)  // 首先将值push到结果中
            stack.push(root)	// 后续遍历 根结点入栈，所有右子树依次入栈
            root = root.right
        }
        root = stack.pop()  //出栈 如果没有左结点继续出栈
        root = root.left
    }
    return res.reverse() //  遍历顺序为根右左 ，最后将 根右左 => 左右根
 };

可以发现我只改动了五行代码,改变他们的顺序，即可完成前中后续遍历，前中后迭代框架大致为：

while(root) {         
         res.push(root.val)  // 首先将值push到结果中
         stack.push(root)	
         root = root.right
       }
       root = stack.pop()  //出栈 
       root = root.left

二叉树的层序遍历(bfs)（leecode102）

leetcode-cn.com/problems/bi…

给定一个二叉树，返回其按层序遍历得到的节点值。 层序遍历即逐层地、从左到右访问所有结点

思路

   广度优先遍历是按层层推进的方式，遍历每一层的节点。要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。

var levelOrder = function(root) {
    if (root === null)  return []
    var arr = []  //广度优先需要用队列作为辅助结构
    var res = []
    arr.push(root) 
    while(arr.length !== 0) {
        var array = []
        var size = arr.length
        for(var i = 0;i<size;i++) {
             var cur = arr.shift()  // 首先拿出根节点
             array.push(cur.val)
            if(cur.left!=null) { //如果左子树/右子树不为空，就将他们放入队列中。
            	arr.push(cur.left)
            } 
         	if(cur.right!=null) {
             	arr.push(cur.right)
            } 
        }
       // 第一遍处理完后，根节点已经从队列中拿走了，而根节点的两个孩子已放入队列中了
     res.push(array) // 将每次的结果保存
     //每次循环 将  从队列中所有结点拿走，然后再将子节点放入队列中。
    }
    return res
};