二叉树的遍历

         二叉树的遍历问题是二叉树的基本核心问题，其他的所有问题基本都是在利用遍历来进行求解，遍历是访问所有的元素并打印或保存访问的元素，而其他问题也是访问所有元素，只不过有特殊的对访问元素的处理操作，因此基本所有问题都是遍历问题的改动。有时二叉树的遍历题目还需要结合集合类的工具，collection中的集合工具对数据进行操作。

          二叉树的遍历常见的有先序、中序、后序、层序，这四种遍历方法，在此基础之上，稍加改动就能实现其他的遍历逻辑，因此在熟练这四种遍历的基础之上，根据题目要求，改动这四种遍历方法中单步的处理，便可以实现其他的遍历操作。基于这四种遍历可以实现非常多变的处理逻辑，比如先序遍历，先处理中间节点这毋庸置疑，那处理完中间节点之后呢？先递归处理左子树还是递归处理右子树？这就要看题目的处理逻辑要求了。同样的中序和后序遍历也是如此，究竟是先递归处理左子树还是先递归处理右子树，这就要根据题目要求来选择是要实现从右向左的处理逻辑，还是从左到右的处理逻辑。

         二叉树的先序、中序、后序、层序遍历非常重要，一定要多思考每一种遍历的处理路径，对树的节点的访问顺序，针对不同的题目，思考哪一种遍历更符合题目的处理要求，然后运用适合的遍历方式，不要习惯性地使用先序遍历。

         二叉树的正常层序遍历，即从二叉树的根节点开始，每次访问一层，将一层中的所有节点从左至右依次处理完后，再开始下一层，直到处理完最下面一层，结束。

         二叉树的倒序层序遍历，即从二叉树的最后一层开始，每次访问一层，将一层中的所有节点右至左依次处理完后，在开始处理上一层，知道处理完根节点所在层，结束。

1、二叉树的正常层序遍历。

        前中后序遍历的递归方法便于理解和接受，不同于这三种常见的遍历方法，层序遍历的非递归方法更容易理解和使用，通过一个队列来完成一颗二叉树的层序遍历，将二叉树的根节点入队列，则当前节点为二叉树的根节点，当前节点也是队列的头元素，判断队列是否有头元素，若有则将头元素（当前节点出队列），访问该节点中存储的数值，并判定该节点的左子节点是否为null，若不是null则将其入队列，接着判断该节点的右子节点是否为null，若不是null则将其入队列，接着判断当前节点是否有头元素......一直循环至队列中不再有头元素，也就是队列中不再有元素，则遍历完成。

public class levelOrder{
    public void levelOrderIterator(BinaryTreeNode root){
        if(root == null){
            return;
        }
        Queue<int> q = new LinkedList<int>();
        BinaryTreeNode currentNode;
        q.offer(root);
        while(!q.isEmpty()){
            //头元素出队列，并进行处理
            currentNode = q.poll();
            //省略了对currentNode中的值currentNode.val进行处理的代码
            //判断当前节点的左右子节点是否为空，若不是null则入队列
            if(currentNode.left != null){
                q.offer(currentNode.left);
            }
            if(currentNode.right != null){
                q.offer(currentNode.right);
            }
        }
    }
}

leetcode 637题可以采用二叉树的层序遍历来解决，一下是题目描述及解决代码

题目描述：

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

输入:
    3
   / \
  9  20
    /  \
   15   7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].

注意：

1. 节点值的范围在32位有符号整数范围内。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //32位有符号整数可以用int
    //需要计算每一层的所有节点的值的和，并统计每一层的节点个数
    //从而计算出每一层的平均数并保存到数组中
    //返回值为List<Double> 可以用ArrayList<Double>
    //采用层序遍历
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode currentNode;
        
        //用于存储每一层的均值，最终返回此链表
        List<Double> result = new ArrayList<Double>();
        //标志位，控制内层循环，即控制求树中一层的节点中数值的和
        int counter = 0;
        //树中一层的节点总数
        int number = 0;
        //树中一层的节点中数值的和
        double sum = 0.0;
        
        q.offer(root);
        while(!q.isEmpty()){
            number = q.size();
            counter = number;
            while(counter != 0){
                currentNode = q.poll();
                if(currentNode.left != null){
                    q.offer(currentNode.left);
                }
                if(currentNode.right != null){
                    q.offer(currentNode.right);
                }
                sum += currentNode.val;
                counter--;
            }
            result.add(sum / number);
            sum = 0.0;
        }
        
        return result;
    }
}

2、二叉树的倒序层序遍历

leetcode 107题便是二叉树的倒序层序遍历，以下是题目描述和代码，思路在代码的注释中。

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

题目描述：

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为：

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //思路一
    //类似于二叉树的从上向下的层序遍历
    //从上向下的层序遍历是用队列，先进先出，而且是每层从左到右入队列
    //从下向上的层序遍历用栈刚好与队列反向，刚好实现后进先出，而且每层从右向左入栈
    //将树从根节点开始入栈，全部入栈后，从栈顶开始输出
    //
    //思路二
    //按照常用的二叉树层序遍历方法，用队列、每层从左到右依次遍历
    //最终结果的list做一次翻转
    //下面用思路二实现
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        int counter = 0;
        
        if(root == null){
            return result;
        }
        
        TreeNode currentNode;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> temp = new ArrayList<Integer>();
            counter = q.size();
            while(counter>0){
                currentNode = q.poll();
                if(currentNode.left != null){
                    q.offer(currentNode.left);
                }
                if(currentNode.right != null){
                    q.offer(currentNode.right);
                }
                temp.add(currentNode.val);
                counter--;
            }
            result.add(temp);
        }
        for(int i=result.size()-1;i>=0;i--){
            result.add(result.remove(i));
        }
        return result;
    }
}

3.二叉搜索树的遍历，其实仍然是二叉树的遍历问题，只不过多了搜索树的特性，中间节点大于左子树所有节点，中间节点小于右子树所有节点

下面这道二叉搜索树的遍历问题的思考解决过程非常重要，写出代码来不是最终目的，如何思考解决问题才是重点，仔细品味每一行代码的作用，为何这么写？

leetcode538把二叉搜索树转换为累加树

题目描述:

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

解决思路（见注释）及代码：

class Solution {
    //首先想到如下思路
    //采用中序遍历，因为二叉搜索树的“左中右-小大更大”的特殊结构，使得处理中间节点必须在中间
    //因此采用中序遍历，左中右的顺序
    //然而中序遍历无法解决，试想一下，二叉搜索树的最小的节点在最左下角
    //其应小于其余所有节点，故应当将其余所有节点加起来
    //但是如何实现其余所有节点求和呢？显然这种思路有问题
    //然后想到如下思路
    //问题不能得到解决的原因是，无法求和，我们应当从“对偶问题”的角度思考，类似于通信中的“对称”思考
    //采用右中左的中序遍历顺序？
    //刚刚好！
    //首先计算右边节点的新值然后中间节点的新值最后是左边节点的新值
    //需要保存上次处理的节点得到的和值
    //刚好实现了从右往左（从大到小），依次处理
    int preSum = 0;
    public TreeNode convertBST(TreeNode root) {
        sumBST(root);
        return root;
    }
    private void sumBST(TreeNode root){
        //递归深层终止返回
        if(root == null){
            return;
        }
        //中序遍历，递归处理右子树
        if(root.right != null){
            sumBST(root.right);
        }
        //中序遍历，处理中间节点
        //叶子节点完全可以视作中间节点，只不过其左右子树均为null
        root.val += preSum;
        preSum = root.val;
        //中序遍历，递归处理左子树
        if(root.left != null){
            sumBST(root.left);
        }
    }
}

4.下面这道题名为二叉树的最小深度，实为遍历题，仔细品味这道题的逻辑处理，对基础先序遍历做的哪些改动？

题目描述：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度  2.

解决思路及代码：

class Solution {
    //采用中序遍历，中左右的顺序
    public int minDepth(TreeNode root) {
        return depth(root);
    }
    private int depth(TreeNode root){
        //深层递归终止退出
        if(root == null){
            return 0;
        }
        //中序遍历，先处理中间节点
        int dep = 0;
        dep++;
        //中序遍历，后处理左右子树
        //根据题目要求，对左右子树进行逻辑处理
        //递归计算左右子树的深度，取较小者
        int tempLeft = 0;
        int tempRight = 0;
        if(root.left != null){
            tempLeft = depth(root.left);
        }
        if(root.right != null){
            tempRight = depth(root.right);
        }
        if(tempLeft != 0 && tempRight != 0){
            dep += Math.min(tempLeft, tempRight);
        }
        if(tempLeft == 0){
            dep += tempRight;
        }
        else if(tempRight == 0){
            dep += tempLeft;
        }
        
        return dep;
    }
}

5.二叉树中第二小的节点，二叉树中最小的节点，二叉树中最大的节点，二叉树中第二大的节点等等，这种题目明显是遍历题目，只不过遍历不是访问所有元素并保存或打印，而是要找出最小、最大等等元素，只是在遍历的基础上，在访问节点后加入特殊的处理操作，这里就是访问元素并比较大小，得到最小的和第二小的。

leetcode671 二叉树中第二小的节点

题目描述：

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

示例 1:

输入: 
    2
   / \
  2   5
     / \
    5   7

输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。

示例 2:

输入: 
    2
   / \
  2   2

输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。

解决思路：

思路一，先序遍历二叉树，将所有的节点值保存到一个线性表中，然后将线性表排序，后输出最小的和第二小的值，太繁琐，而且运行速度可肯定慢
思路二，先序遍历二叉树，维护两个变量，保存最小值和第二小值

class Solution {
    //思路一
    //先序遍历二叉树，将所有的节点值保存到一个线性表中
    //然后将线性表排序，后输出最小的和第二小的值
    //太繁琐，而且运行速度可肯定慢
    //思路二
    //先序遍历二叉树，维护两个变量，保存最小值和第二小值
    int min = Integer.MAX_VALUE;
    int minSecond = Integer.MAX_VALUE;
    public int findSecondMinimumValue(TreeNode root) {
        find(root);
        return minSecond==Integer.MAX_VALUE ? -1 : minSecond;
    }
    private void find(TreeNode root){
        //递归结束返回
        if(root == null){
            return;
        }
        //处理中间节点，遍历时的处理为简单的保存或打印
        //这里的处理为比较当前节点中值最目前最小，第二小的大小关系
        //将最小的保存在min中，第二小的保存在minSecond中
        if(root.val <= min){
            min = root.val;
        }
        else if(root.val <= minSecond){
            minSecond = root.val;
        }
        //递归处理左右子树
        find(root.left);
        find(root.right);
    }
}

6. 二叉树的遍历题目，但是使用集合接口中的实现类来对数据进行操作。

leetcode 653两数之和IV-输入BST

题目描述：

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

解决思路：用一个set实现类的对象保存已经处理过的节点的数据，先序遍历所有的节点，首先处理当前节点，对于当前节点的值，首先判断set中是否存在一个值与当前节点值和为目的和值（这个操作可以利用set实现类的contains方法，是否包含目的值减去当前节点值），若存在则返回true，完成；若不存在，则递归处理左右子树，只要左右子树中有一个返回true，最终就是true，若都是false，则最终返回false。

代码：

class Solution {
    //需要查看任意两个元素的和是否为目标值
    //即任意两个节点的和是否为target
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> hashset = new HashSet<Integer>();
        return find(root, hashset, k);
    }
    private boolean find(TreeNode root, HashSet<Integer> hashset, int target){
        if(root == null){
            return false;
        }
        
        if(hashset.contains(target-root.val)){
            return true;
        }
        hashset.add(root.val);
        
        return find(root.left, hashset, target)||find(root.right, hashset, target);
    }
}