二叉树层序遍历

文章：5. 二叉树的层序遍历

层序遍历：广度搜索

102.二叉树的层序遍历

题目：102. 二叉树的层序遍历

【思路】

层序遍历一个二叉树，就是用左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前见过的都不太一样。需要借助一个辅助数据结构，即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历，也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先搜索，只不过是应用在了二叉树上。

Java实现

递归实现

class Solution {
    public List<List<Integer>>resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFunc(root,0);
        return resList;
    }
    //DFS-递归方式
    public void checkFunc(TreeNode node,Integer deep){
        if (node == null)return;
        deep++;
        if(resList.size() < deep){
            //为当前层创建一个新的空列表，用来存储该层级的节点值
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep-1).add(node.val);
        checkFunc(node.left,deep);
        checkFunc(node.right,deep);
    }
}

队列实现

class Solution {
    public List<List<Integer>>resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
       chechFunc(root);
       return resList; 
    }

    //BFS-迭代方式-借助队列
    public void chechFunc(TreeNode node){
        if(node == null) return ;
        Queue<TreeNode>que = new LinkedList<>();
        que.add(node);

        while(!que.isEmpty()){
            List<Integer>item = new ArrayList<>();
            int len = que.size();
            while(len>0){
                TreeNode temNode = que.poll();
                item.add(temNode.val);
                if(temNode.left!=null)que.add(temNode.left);
                if(temNode.right != null)que.add(temNode.right);
                len--;
            }
            resList.add(item);
        }
    }
    
}

Go实现

DFS-递归实现

func levelOrder(root *TreeNode) [][]int {
    //二叉树的递归实现
    //需要使用一个二维数组来记录结果
    ans :=[][]int{}
    depth :=0
    var checkFunc func(root *TreeNode,depth int)
    checkFunc =func(root *TreeNode,depth int){
        if root == nil{
            return 
        }
        if len(ans) == depth{
            ans = append(ans,[]int{})
        }
        ans[depth] = append(ans[depth],root.Val)

        checkFunc(root.Left,depth+1)
        checkFunc(root.Right,depth+1)
    }
    checkFunc(root,depth)
    return ans
}

层序遍历

链表法（？）

func levelOrder(root *TreeNode) [][]int {
    //二叉树的层序遍历实现
    //需要使用一个二维数组来记录结果
    
    res :=[][]int{}
    if root == nil{
        return res 
    }
    queue := list.New()
    queue.PushBack(root)

    for len(queue) > 0{
        //提前保留当前层的长度
        lenth := queue.Len()
        //从左到右 遍历当前层的节点
        for i :=0;i< lenth;i++{
            node := queue.Remove(queue.Front()).(*TreeNode)
            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right!=nil{
                queue.PushBack(node.Remove)
            }
            temArr = append(temArr,node.Val)//收集本层节点
        }
        res = append(res,temArr)//将收集好的本层节点集放入结果集
        temArr = []int{}//清空当前层的结果集
    }
    return res
}

切片法（？）

func levelOrder(root *TreeNode) (res [][]int) {
    //二叉树的层序遍历实现
    //需要使用一个二维数组来记录结果
    if root == nil{
        return 
    }
    curLevel := []*TreeNode{root}
    for len(curLevel) >0 {
        nextLevel := []*TreeNode{}
        vals := []int{}
        for _,node := range curLevel{
            vals = append(vals,node.Val)//收集当前层的节点
            if node.Left != nil{
                nextLevel = append(nextLevel,node.Left)
            }
            if node.Right !=nil{
                nextLevel = append(nextLevel,node.Right)
            }
        }
        res = append(res,vals)
        curLevel = nextLevel
    }
    return 
}

107.二叉树的层序遍历II

题目：107. 二叉树的层序遍历 II

【思路】

只需要将二叉树层序遍历后的结果reverse一下就好啦

Java实现

新建一个lists存储一开始的结果，然后再用for循环将lists的值倒序加入res就可以啦。

class Solution {
    public List<List<Integer>>res = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        checkFunc(root);
        return res;
    }
    public void checkFunc(TreeNode root){
        List<List<Integer>>lists = new ArrayList<List<Integer>>();
        if(root == null)return ;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            List<Integer>item = new ArrayList<>();
            int len = queue.size();

            while(len > 0){
                TreeNode node = queue.poll();
                item.add(node.val);
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
                len--;
            }
            lists.add(item);
        }

        for(int i = lists.size()-1;i>=0;i--){
            res.add(lists.get(i));
        }
    }
}

Go实现

感觉还是切片法比较适合我

func levelOrderBottom(root *TreeNode)(res [][]int) {
    if root == nil{
        return
    }
    curLeven :=[]*TreeNode{root}
    //如果切片不为空
    for len(curLeven) > 0{
        nextLevel := []*TreeNode{}
        vals := []int{}//当前层的结果集切片
        //遍历切片
        for _,val := range curLeven{
            //收集当前层的节点
            vals = append(vals,val.Val)
            if val.Left != nil{
                nextLevel = append(nextLevel,val.Left)
            }
            if val.Right != nil{
                nextLevel = append(nextLevel,val.Right)
            }
        }
        res = append(res,vals)
        curLeven = nextLevel
    }
    reverse(res)
    return 
}

func reverse(arr [][]int){
    l , r:= 0,len(arr)-1
    for l < r {
        arr[l] ,arr[r] = arr[r],arr[l]
        l++
        r--
    }
}

199.二叉树的右视图

题目：199. 二叉树的右视图

【思路】

右视图，只需要返回当前层的最后一个节点就好了噢！

Java实现

class Solution {
    public List<Integer>res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        checkFunc(root);
        return res;
    }
    public void checkFunc(TreeNode root){
        if(root==null)return ;
        Queue<TreeNode>queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            List<Integer>item = new ArrayList<>();
            int len = queue.size();
            while(len >0){
                TreeNode node = queue.poll();
                if(len ==1)res.add(node.val);
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
                len--;
            }
        }
    }
}

Go实现

func rightSideView(root *TreeNode) (res []int) {
    if root == nil{
        return 
    }
    curLevel :=[]*TreeNode{root}
    for len(curLevel) >0 {
        nextLevel := []*TreeNode{}

        for index,node := range curLevel{
            if index == len(curLevel)-1{
                res = append(res,node.Val)
            }
            if node.Left != nil{
                nextLevel = append(nextLevel,node.Left)
            }
            if node.Right != nil{
                nextLevel = append(nextLevel,node.Right)
            }
        }
        curLevel = nextLevel
    }
    return 
}

637.二叉树的层平均值

题目：637. 二叉树的层平均值

【思路】

在每层遍历完当前层之后，求item里面值的平均值，再加入res就好啦

Java实现

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if(root == null)return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int len = queue.size();
            while(len>0){
                TreeNode node = queue.poll();
                item.add(node.val);
                if(node.left != null)queue.add(node.left);
                if(node.right!= null)queue.add(node.right);
                len--;//老忘记len--!!
            }
            double sum = 0;
            for(int i = 0 ; i < item.size();i++){
                sum+=item.get(i);
            }
            sum = sum/item.size();
            res.add(sum);
        }
        return res;
    }
}

Go实现

func averageOfLevels(root *TreeNode)(res []float64) {
    if root == nil{
        return 
    }
    curLevel := []*TreeNode{root}
    var sum float64
    for len(curLevel)>0{
        sum =0
        nextLevel := []*TreeNode{}
        length := len(curLevel)
        for _,node := range curLevel{
            sum += float64(node.Val)
            if node.Left != nil{
                nextLevel= append(nextLevel,node.Left)
            }
            if node.Right != nil{
                nextLevel = append(nextLevel,node.Right)
            }
            //老忘记更新level、
        }
        curLevel = nextLevel
        sum = sum/float64(length)
        res = append(res,sum)
    }
    return 
}

老是漏东漏西，忘记len–和更新新的层数！！

429.N叉树的层序遍历

【思路】

从二叉树变成了多叉树

因此我们需要新增一个临时的集合来保存当前层中所有的节点值，最后遍历完了再加入结果集

Java实现

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res  = new ArrayList<List<Integer>>();

        if(root == null)return res;
        Deque<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer>item = new ArrayList<>();
            int len = queue.size();
            while(len >0){
                len--;   //由于下面if判断里面有continue，因此我们需要将len--提到前面去
                Node node = queue.pollFirst();
                item.add(node.val);
                //新建一个变量来存储类型为List的node.children
                List<Node>children = node.children;
                //判断是否为空
                if(children == null || children.size()==0){
                    continue;
                }
                //不为空的话，就遍历添加进queue里面去
                for(Node child : children){
                    queue.offerLast(child);
                }
            }
            res.add(item);
        }
        return res;

    }
}

Go实现

要遍历完当前层的所有节点才能加进结果集里面噢！

func levelOrder(root *Node) (res [][]int) {
    if root ==nil{
        return 
    }
    curLevel := []*Node{root}
    for len(curLevel)>0{
        nextLevel := []*Node{}
        //遍历
        var temp []int//要遍历完当前层的所有节点才能加进结果集里面噢！
        for _,node := range curLevel{
            temp = append(temp,node.Val)
            children := node.Children
            if children == nil{
                continue
            }
            for _,child := range children{
                nextLevel = append(nextLevel,child)
            }

        } 
        res = append(res,temp)
        curLevel = nextLevel
    }
    return
}

515.在每个树中找最大值

题目：515. 在每个树行中找最大值

【思路】

层序遍历，找到每一层的最大值。

Java实现

class Solution {
    public List<Integer> largestValues(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       if(root == null)return res;
       Queue<TreeNode> queue = new LinkedList();
       queue.add(root);
       while(!queue.isEmpty()){
           List<Integer>item = new ArrayList<>();
           int len = queue.size();
           while(len > 0){
               TreeNode node = queue.poll();
               item.add(node.val);
               if(node.left!= null)queue.add(node.left);
               if(node.right!= null)queue.add(node.right);
               len--; 
           }
           res.add(max(item));

       } 
       return res;
    }
    public int max(List<Integer>item){
        int max = item.get(0);
        for(int i : item){
            if(max <i)max =i;
        }
        return max;
    }
}

Go实现

func largestValues(root *TreeNode) (res []int) {
    if root == nil{
        return 
    }
    curLevel :=[]*TreeNode{root}
    for len(curLevel) > 0 {
        nextLevel := []*TreeNode{}
        num := []int{}
        for _,node := range curLevel{
            num = append(num,node.Val)
            if node.Left != nil{
                nextLevel = append(nextLevel,node.Left)
            }
            if node.Right!=nil{
                nextLevel = append(nextLevel,node.Right)
            }
            curLevel = nextLevel
        }
        res = append(res,max(num))
    }
    return 
}

func max(nums []int)int{
    maxN := nums[0]
    for _,num:= range nums{
        if maxN < num{
            maxN = num
        }
    }
    return maxN
}

116.填充每个节点的下一个右侧节点指针

题目：116. 填充每个节点的下一个右侧节点指针

【思路】

层序遍历，只不过在单层遍历的时候记录下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了。

Java实现

class Solution {
    public Node connect(Node root) {
        Queue<Node> temQueue = new LinkedList<>();
        if(root == null){
            return root;
        }
        temQueue.add(root);
        while(temQueue.size()!=0){
            int size = temQueue.size();
            Node cur = temQueue.poll();
            if(cur.left != null) temQueue.add(cur.left);
            if(cur.right!= null) temQueue.add(cur.right);

            for(int index = 1; index < size ;index++){
                Node node = temQueue.poll();
                if(node.left!= null)temQueue.add(node.left);
                if(node.right!=null)temQueue.add(node.right);
                cur.next = node;
                cur = node;//更新到下一个节点
            }
        }
        return root;
    }
}

Go实现

func connect(root *Node) *Node {
    if root == nil{
        return root
    }
	curLevel :=[]*Node{root}
    for len(curLevel) >0{
        nextLevel := []*Node{}
        tempLevel := curLevel
        for _,node := range curLevel{
            if node.Left != nil{
                nextLevel = append(nextLevel,node.Left)
            }
            if node.Right != nil{
                nextLevel = append(nextLevel,node.Right)
            }
            
        }
        for i :=1 ;i<len(tempLevel);i++{
            tempLevel[i-1].Next =tempLevel[i]
        }

        
        curLevel = nextLevel
    }
    return root
}

117.填充每个节点的下一个右侧节点指针II

题目：117. 填充每个节点的下一个右侧节点指针 II

【思路】

和上一题一样，都是遍历循环，存储前一个节点进行填充。

Java实现

class Solution {
    public Node connect(Node root) {
        if(root == null)return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            Node cur = queue.poll();
            if(cur.left!=null)queue.add(cur.left);
            if(cur.right!= null)queue.add(cur.right);
            for(int i = 1 ;i<len;i++){
                Node next = queue.poll();
                if(next.left!=null)queue.add(next.left);
                if(next.right != null)queue.add(next.right);
                cur.next = next;
                cur = next;
            }
        }
        return root;
    }
}

Go实现

func connect(root *Node) *Node {
	 if root == nil{
        return root
    }
	curLevel :=[]*Node{root}
    for len(curLevel) >0{
        nextLevel := []*Node{}
        tempLevel := curLevel
        for _,node := range curLevel{
            if node.Left != nil{
                nextLevel = append(nextLevel,node.Left)
            }
            if node.Right != nil{
                nextLevel = append(nextLevel,node.Right)
            }
            
        }
        for i :=1 ;i<len(tempLevel);i++{
            tempLevel[i-1].Next =tempLevel[i]
        }

        
        curLevel = nextLevel
    }
    return root
}

104.二叉树的最大深度

题目：104. 二叉树的最大深度

【思路】

每层遍历完都判断一次堆是否为空，不为空即深度++

Java实现

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        int depth = 1;
        Queue<TreeNode>queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<TreeNode>item = new ArrayList<>();
            int len = queue.size();
            while(len>0){
                TreeNode node = queue.poll();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                len--;
            }
            if(!queue.isEmpty())depth++;
        }
        return depth;

    }
}

Go实现

func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    depth := 0
    curLevel := []*TreeNode{root}
    for len(curLevel)>0{
        nextLevel := []*TreeNode{}
        for _,node :=range curLevel{
            if node.Left!= nil{
                nextLevel = append(nextLevel,node.Left)
            }
            if node.Right != nil{
                nextLevel = append(nextLevel,node.Right)
            }
        }
        curLevel = nextLevel
        if curLevel!=nil{
            depth++
        }
    }
    return depth
}

111.二叉树的最小深度

题目：111. 二叉树的最小深度

【思路】

只要出现有节点的左右孩子均为空，返回当前的深度就好啦

Java实现

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            depth++;
            for(int i = 0 ; i < size;i++){
                TreeNode node = queue.poll();
                if(node.left == null && node.right==null)return depth;
                if(node.left != null )queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
            }
        }
        return depth;
    }
}

Go实现

func minDepth(root *TreeNode) int {
    ans := 0
    if root == nil{
        return 0
    }
    queue := list.New()
    queue.PushBack(root)
    for queue.Len() >0{
        length := queue.Len()
        for i:= 0 ; i < length;i++{
            node:= queue.Remove(queue.Front()).(*TreeNode)
            if node.Left==nil&& node.Right == nil{
                return ans +1
            }
            if node.Left!=nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
        }
        ans++
    }
    return ans+1
}

226.翻转二叉树

题目：226. 翻转二叉树

【思路】

这道题我刚开始看到的时候大概的思路是想要当前层队列里的节点做一个翻转==全部换个位子，然后想了一下好像不太ok，遂看了一下答案，是在弹出节点时就交换左右孩子就好了。

Java实现

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)return null;
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }
    public void swapChildren(TreeNode node){
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }
}

Go实现

func invertTree(root *TreeNode) *TreeNode {
    if root ==nil{
        return nil
    }
    root.Left ,root.Right = root.Right,root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

总结

对于二叉树节点的定义，C++代码如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Java代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

Go代码如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

周二

在二叉树：一入递归深似海，从此offer是路人 (opens new window)中讲到了递归三要素，以及前中后序的递归写法。

文章中我给出了leetcode上三道二叉树的前中后序题目，但是看完二叉树：一入递归深似海，从此offer是路人 (opens new window)，依然可以解决n叉树的前后序遍历，在leetcode上分别是

大家可以再去把这两道题目做了。

周三

在二叉树：听说递归能做的，栈也能做！ (opens new window)中我们开始用栈来实现递归的写法，也就是所谓的迭代法。

细心的同学发现文中前后序遍历空节点是否入栈写法是不同的

其实空节点入不入栈都差不多，但感觉空节点不入栈确实清晰一些，符合文中动画的演示。

拿前序遍历来举例，空节点入栈：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                      // 中
            st.pop();
            if (node != NULL) result.push_back(node->val);
            else continue;
            st.push(node->right);                           // 右
            st.push(node->left);                            // 左
        }
        return result;
    }
};

前序遍历空节点不入栈的代码：（注意注释部分和上文的区别）

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

在实现迭代法的过程中，有同学问了：递归与迭代究竟谁优谁劣呢？

从时间复杂度上其实迭代法和递归法差不多（在不考虑函数调用开销和函数调用产生的堆栈开销），但是空间复杂度上，递归开销会大一些，因为递归需要系统堆栈存参数返回值等等。

递归更容易让程序员理解，但收敛不好，容易栈溢出。

这么说吧，递归是方便了程序员，难为了机器（各种保存参数，各种进栈出栈）。

在实际项目开发的过程中我们是要尽量避免递归！因为项目代码参数、调用关系都比较复杂，不容易控制递归深度，甚至会栈溢出。

周四

在二叉树：前中后序迭代方式的写法就不能统一一下么？ (opens new window)中我们使用空节点作为标记，给出了统一的前中后序迭代法。

此时又多了一种前中后序的迭代写法，那么有同学问了：前中后序迭代法是不是一定要统一来写，这样才算是规范。

其实没必要，还是自己感觉哪一种更好记就用哪种。

但是一定要掌握前中后序一种迭代的写法，并不因为某种场景的题目一定要用迭代，而是现场面试的时候，面试官看你顺畅的写出了递归，一般会进一步考察能不能写出相应的迭代。

周五

在二叉树：层序遍历登场！ (opens new window)中我们介绍了二叉树的另一种遍历方式（图论中广度优先搜索在二叉树上的应用）即：层序遍历。

看完这篇文章，去leetcode上怒刷五题，文章中编号107题目的样例图放错了（原谅我匆忙之间总是手抖），但不影响大家理解。

只有同学发现leetcode上“515. 在每个树行中找最大值”，也是层序遍历的应用，依然可以分分钟解决，所以就是一鼓作气解决六道了。

层序遍历遍历相对容易一些，只要掌握基本写法（也就是框架模板），剩下的就是在二叉树每一行遍历的时候做做逻辑修改。

周六

在二叉树：你真的会翻转二叉树么？ (opens new window)中我们把翻转二叉树这么一道简单又经典的问题，充分的剖析了一波，相信就算做过这道题目的同学，看完本篇之后依然有所收获！

文中我指的是递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。

如果非要使用递归中序的方式写，也可以，如下代码就可以避免节点左右孩子翻转两次的情况：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

代码虽然可以，但这毕竟不是真正的递归中序遍历了。

但使用迭代方式统一写法的中序是可以的。

代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

为什么这个中序就是可以的呢，因为这是用栈来遍历，而不是靠指针来遍历，避免了递归法中翻转了两次的情况，大家可以画图理解一下，这里有点意思的。

#总结

本周我们都是讲解了二叉树，从理论基础到遍历方式，从递归到迭代，从深度遍历到广度遍历，最后再用了一个翻转二叉树的题目把我们之前讲过的遍历方式都串了起来。