Java实现二叉树的相关问题(1)

数据结构——二叉树

V表示根结点，L表示左孩子（左子树），R表示右孩子（右子树）

持续更新内容之树结构算法，主要是分析与解决相关二叉树的问题，主要包括有
1.树的遍历（先序，中序，后序，层序(BFS)）
2.树的深度计算
3.对称二叉树的判断
4.BST（二叉搜索树）的判断
5.二叉树的路径搜索

树的遍历的名称是由根节点遍历的顺序来确定的，如下详解。

根节点先遍历，然后是左树，然后是右树，无论是从整体看，还是从局部的子树来看都是符合此顺序。

左|中|右的遍历方式，即先遍历左树，然后是中间的根结点。

左|右|中的遍历顺序，即先遍历左树，然后是右树，最后是根结点，无论是局部还是整体来看，均是如此

顾名思义，一层一层的遍历树。

二叉树与之前所学的内容有着一个很大不同的地方，便是局部与整体的结构都是相似的，非常适合使用递归实现相关问题的解决，当然只是掌握递归的方法是不够，还需要掌握使用遍历的方法解决相关问题，二叉树问题中使用迭代解决，一般需要引入两种数据结构，栈(stack)，队列(queue)，针对问题的不同选择不同特点的结构，栈——先进后出，队列——先进先出。
创建一棵树，用于实现以上算法：

TreeNode tr = new TreeNode(1);
tr.right = new TreeNode(2);
tr.left = new TreeNode(3);
tr.left.right = new TreeNode(4);
tr.right.left = new TreeNode(5);
tr.right.right = new TreeNode(6);

首先是递归实现如下：

    private static void preOrder(TreeNode root) {
        if (root == null)  //为空时说明迭代应该终止了
            return;

        System.out.print(root.val + " ");   //根结点输出
        preOrder(root.left);				//左树进入迭代
        preOrder(root.right);				//右树进入迭代
    }

//输出结果
1 3 4 2 5 6

分析： 迭代较为关键的一点是中止条件，也就是上面的为空时，返回void。先序遍历的方式是，中|左|右，也就是说中间的先遍历，故先输出root.val，然后进入左中遍历，先序遍历无论是局部还是整体，都是符合上述的遍历顺序，故当左树遍历结束后，会进入右树。

迭代实现：
若用迭代的方式实现，则需要引入栈结构，代码如下：

    private static void preOrder01(TreeNode root) {
        if (root ==  null)
            return;

        Stack stack = new Stack<>();
        stack.push(root);    //根节点入栈，使得判定条件能够触发

        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();   //弹出栈顶，即当前结点
            System.out.print(cur.val + " ");
            if (cur.right != null)		//若右结点存在，右结点进入
                stack.push(cur.right);
            if (cur.left != null)		//若左结点存在，左结点进入
                stack.push(cur.left);
        }
    }
    
//输出结果
1 3 4 2 5 6

与上面递归不同的是，右结点先进入，然后是左结点进入，这是与栈结构的特点有关——先进后出，若右结点新进入，会被压栈底，输出的时候则会在最后输出，流程如下：

入栈判断是，看是否存在右左子树。图中只画了一个入栈过程，没有全部画出。

左|中|右遍历方式，先左树遍历完，然后根结点，最后进入右树，递归实现如下：

    private static void inOrder(TreeNode root){
        if (root == null)
            return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    
//运行结果
3 4 1 5 2 6

开始直接找到左树的叶结点，然后向上，遍历完左树，进入右树遍历。

迭代实现：
不妨考虑递归是如何实现的，将递归遍历的顺序改为利用迭代实现即可，递归首先找到左树的最左边的叶结点，然后根，右子结点。迭代实现的思想也是如此，首先将左结点全部入栈，然后输出，右结点入栈。

    private static void inOrder01(TreeNode root){
        if (root == null)
            return;
        Stack stack = new Stack<>();
        while (true){  //反复执行
            while (root != null ){  //从当前结点出发，逐批入栈
                stack.push(root);
                root = root.left;
            }

            if (stack.isEmpty())   //所有结点处理完毕，跳出循环
                break;

            root = stack.pop();   //root的左树为空，才会执行以下语句
            System.out.print(root.val + " ");
            root = root.right;    //转向右子树

        }
    }
    
//运行结果
3 4 1 5 2 6

左|右|中遍历方式，先将右树遍历完毕，然后遍历左树，最后遍历根结点，递归实现如下：

    private static void postOrder(TreeNode root){
        if (root == null)
            return;

        postOrder(root.right);
        postOrder(root.left);
        System.out.print(root.val + " ");
    }

//运行结果
6 5 2 4 3 1 

若使用迭代的写法，则可以观察到，先序遍历与后序遍历是相反，不妨再添加一个栈，存储先序栈的输出，最后将val输出，迭代实现如下：

    private static void postOrder01(TreeNode root){
        if (root == null)
            return;

        Stack stack = new Stack<>();
        Stack stack1 = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            stack1.push(cur);     //将前面栈的输出全部存储下来
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }

        while (!stack1.isEmpty())
            System.out.print(stack1.pop().val + " ");
    }

//运行结果
6 5 2 4 3 1 

层序遍历，是一层一层的进行遍历，可以获得树的深度，以及每层的结点，层序遍历，需要引入队列结构，先入先出。使用迭代实现如下：

    private static void levelOrder(TreeNode root){
        if (root == null)
            return;

        Queue queue = new linkedList<>();   //队列可以看成链表
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
        }
    }
    
//运行结果
1 3 2 4 5 6 

根结点入队，左树入，右树入，如果想把遍历的结果存放到list中，需要知道每层的个数，即需要遍历queue的次数，代码实现如下：

private static List> levelOrder01(TreeNode root){
    if (root == null)
        return new ArrayList<>();
    List> res = new ArrayList<>();
    Queue queue = new linkedList<>();

    queue.add(root);

    while (!queue.isEmpty()){
        int levelNum = queue.size();  //获得队列的长度，即需要遍历的次数
        List temp = new ArrayList<>();  //建立列表存放每行的结点值

        for (int i = 0; i < levelNum; i++) {
            TreeNode cur = queue.poll();
            temp.add(cur.val);
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
        }
        res.add(temp);
    }

    return res;
}

//运行结果
[[1], [3, 2], [4, 5, 6]]

树的遍历的问题就这些，本人感觉比较重要的是学会运用递归去解决问题，因为树的整体和局部非常相似，非常适合递归的使用，用好了递归，很多问题都能迎刃而解，当迭代的方法也是需要掌握的，两者之间是存在一定联系的，最好都掌握。