[数据结构与算法]剑指offer 深度优先遍历（DFS）和广度优先遍历（BFS） 题解一

深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search)是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路(走迷宫)，搜索引擎，爬虫等，算面试高频考点

常见的 DFS ： 先序遍历、中序遍历、后序遍历；
常见的 BFS ： 层序遍历（即按层遍历）。

1.剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

题解

/方法1：使用递归的方法
//蜜汁自信法，也就是解决问题时需要递归调用主方法，我们就认为问题已经得到解决，调用相应方法就行。
public TreeNode mirrorTree(TreeNode root) {
    if(root==null){
        return null;
    }
    //左节点暂存，不暂存的话，后面root.left就是新的left了
    TreeNode tmp=root.left;
    root.left=mirrorTree(root.right);
    root.right=mirrorTree(tmp);
    return root;
    }

方法2：使用栈（大多数情况使用栈比较好，递归效率较慢）
 class Solution {
        //使用栈的先进后出特性
        public TreeNode mirrorTree(TreeNode root) {
            if(root==null){
                return null;
            }
            Stack<TreeNode> stack=new Stack<>();
            stack.push(root);
            //栈为空，即所有节点都弹出时，此时镜像功能已经完成，退出循环
            while(!stack.isEmpty()){
                //先弹出一个节点
                TreeNode node=stack.pop();
                //将弹出节点的左右节点加入栈
                if(node.left!=null){
                    stack.push(node.left);
                }
                if(node.right!=null){
                    stack.push(node.right);
                }
                //暂存左节点
                TreeNode tmp=node.left;
                //左右节点交换
                //右节点付给左节点
                node.left=node.right;
                //左节点赋给右节点
                node.right=tmp;
            }
            //功能完成，返回根节点
            return root;
        }
    }

2.剑指 Offer 28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

        例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

            1
           / \
          2   2
         / \ / \
        3  4 4  3
        但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

            1
           / \
          2   2
           \   \
           3    3

         

        示例 1：

        输入：root = [1,2,2,3,4,4,3]
        输出：true
        示例 2：

        输入：root = [1,2,2,null,3,null,3]
        输出：false

题解：

class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root==null? true:recur(root.left,root.right);

        }
        //定义一个方法，不断从根节点递归遍历，如果不满足退出条件就往下走，这样整个树走完后，就是对称树，如果中途不是，就会退出
        public boolean recur(TreeNode l,TreeNode r){
            //递归终止条件
            //1.从上到小所有节点都对称
            if(l==null && r==null){
                return true;
            }
            //2.其中右一个为空，或者对称位置值不相等
            if(l==null||r==null||l.val!=r.val){
                return false;
            }
            return recur(l.left,r.right)&&recur(l.right,r.left);
        }
    }

3.剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

         

        例如:
        给定二叉树: [3,9,20,null,null,15,7],

        3
        / \
        9  20
        /  \
        15   7
        返回：

        [3,9,20,15,7]

题解

class Solution {
        //本题考察二叉树的广度优先搜索(层序遍历)，一般使用队列实现
        public int[] levelOrder(TreeNode root) {
            if(root==null){
                return new int[0];
            }
            //定义一个队列(栈和队列都是集合，可以使用链表LinkedList表示，会加快速度)
            Queue<TreeNode> queue=new LinkedList<>();
            //先将根节点加入队列
            queue.offer(root);
            ArrayList<Integer> ans=new ArrayList<>();
            while(!queue.isEmpty()){
                //将节点弹出队列
                TreeNode node=queue.poll();
                //获取所弹出队列节点的值
                ans.add(node.val);
                //将左节点加入队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                //将右节点加入队列
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //将集合转化为数组
            int[] res=new int[ans.size()];
            for(int i=0;i<res.length;i++){
                res[i]=ans.get(i);
            }
            return res;
        }
    }

4.剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

         

        例如:
        给定二叉树: [3,9,20,null,null,15,7],

        3
        / \
        9  20
        /  \
        15   7
        返回其层次遍历结果：

        [
        [3],
        [9,20],
        [15,7]
        ]

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null) queue.add(root);
            while(!queue.isEmpty()) {
                List<Integer> tmp = new ArrayList<>();
                for(int i = queue.size(); i > 0; i--) {
                    TreeNode node = queue.poll();
                    tmp.add(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
                if(res.size() % 2 == 1) Collections.reverse(tmp);
                res.add(tmp);
            }
            return res;
        }
    }

5.剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

         

        例如:
        给定二叉树: [3,9,20,null,null,15,7],

        3
        / \
        9  20
        /  \
        15   7
        返回其层次遍历结果：

        [
        [3],
        [20,9],
        [15,7]
        ]

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            List<Integer> list=new ArrayList<>();
            for(int i=queue.size();i>0;i--){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //通过奇偶判断将正序和倒叙分开
            if(res.size()%2==1){
                Collections.reverse(list);
            }
            res.add(list);
           
        }
        return res;
    }
}