树算法系列 一 树的遍历与LeetCode相关树遍历算法

引言

众说周知，树在算法领域算是一个比较大的分支结构。其中的对于树及基础的遍历，以及对于各种遍历情况下的衍生出来的也是层出不穷，今天就来记录在学习过程中遇到的一些基础的遍历过程中的算法题目，也是系列的第一讲。
注：以下所有代码皆使用Java进行编写

树的各种遍历：

首先我们需要了解一下数的各种遍历：分为先序，中序，后序，层序；
讲解：对于树的操作而言，由于在很多的情况下都是会回退到对上一级的访问，所以在对于树的算法中很多的情况在在遍历的过程中会常常使用到栈（先入后出），队列（先入先出），或者是直接只用到递归来进行解题，因为对于递归来说，在特定的时候，进行一个判断，就能够很好的回退到对上一层的操作上面。当然泛泛而谈也不是我们的特点，下面我来具体的讲解各种的遍历操作，以及在LeetCode上面，对于树的遍历的一部分题型。

树的数据结构：

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

前序遍历

先序：根->左子树->右子树；
思想：： 提及到先序遍历（这里我就不再画具体的图来进行解释什么是先序遍历）我们所有的序操作都是对于根节点来说，所以先序是先进性根节点，然后左子树，然后再右子树。此时想到前面所提及到的基础的使用方法。可以使用到栈来进行一个辅助，但是此时又出现了一个问题，对于栈来说是先进后出，我们想要实现访问完根节点能够对右子树进行输出，所以此时就不能够先把右子树放进去，先放左子树，然后再放右子树，就可以实现我们想要实现的操作。
代码展示：

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList <Integer> array=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode> ();
        if(root==null)
            return array;
        stack.push(root);
        while(!stack.isEmpty()){
           TreeNode temp=stack.pop();
            array.add(temp.val);
            if(temp.right!=null){
                stack.push(temp.right);
            }
            if(temp.left!=null)
                stack.push(temp.left);
        }
        return array;
    }
}

讲解：：首先我们要解决的问题：

1. 使用到什么数据结构，这里也算是提醒大家，在树的操作中，不是栈就是队列，当然栈的操作会更多，也更加符合树的特性，然后就是使用链表来进行接收操作。
2. 由于之前讲过，实现根->左->右,但是对于栈的操作却是要反而行之，由于每一个小的子树却也都是一课子树，所以在操作时候，要放在一个循环中进行执行。
3. 使用一个pop出来的值，进行左右操作，就可以解决上一阶级的问题。

中序遍历

左->根->右
思想： 既然是先左子树，我们要解决的第一个问题就是说对于很多层的，我们首先要做的肯定就是使用一个while循环知道位于树的最底层的最左边的一个节点。然后在一些的节点不存在时候，适当进行pop依次得到上一层的节点的信息，再度进行另外一边节点的操作。
代码：

import java.util.*;
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> array=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
        if(root==null) return array;
      //  stack.push(root);
        TreeNode node=root;
        while(node!=null ||!stack.isEmpty()){
            while(node!=null){ 
                stack.push(node);
                node=node.left;
            }
                  TreeNode temp=stack.pop();
                  array.add(temp.val);
                  node=temp.right;
        }
         return array;
    }
}

讲解：：如上我们可以看到的是，同先序遍历的大值思想是一致的，进行栈的判空是为了能够判断是否对整个树都进行扫描。同样先进入到最底端的左节点，然后不成功时候再度向上一级索引（这里就会使用到栈的pop()）。然后再循环操作即可。

后序遍历

左->右->根
思路: 和先序遍历的情况正好相反，此时我们可以设想一下，在先序中，我们对于根来说，根在前，然后是左右。此时的情况是，根在后，然后左右在前。此时我们可以转换思路，既然现在情况是 根在最后，不如我们照常来进行遍历，最后都压在一个栈中，然后，统一对栈进行pop() 时候，即可完成我们想要的需求，但是此时有一个问题，队友左右根的出栈，就是，根右左的压栈，此时，右先左的前面，所以此时，先遍历左子树，再度进行右子树。

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> array=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
         Stack<TreeNode> stacks=new Stack<TreeNode>();
        if(root==null)
            return array;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode temp =stack.pop();
            stacks.push(temp);
            if(temp.left!=null){
            stack.push(temp.left);
            }
            if(temp.right!=null)
            stack.push(temp.right);
        }
        while(!stacks.isEmpty()){
            TreeNode c=stacks.pop();
            array.add(c.val);
        }
        return array;
        
    }
}

层序遍历 使用到了 队列

思路： 层序遍历，顾名思义，就是对于树的一层一层组成遍历，不同于之前讲到的遍历而言，逐层遍历，不需要再次进行左右的切换，此时也不需要用到栈的那种特性，但是此时思考的问题是：“如何在访问完一个根节点的左右子树之后，再度返回到由右子树组成的一个小的子树，此时就使用到了队列的特性、先访问的左子树，也是先进入队列，然后对于先进入的再次先进行访问，也是满足我们的需求–从左到右的依次。”

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
         Queue<TreeNode> queue=new LinkedList<TreeNode>();
         ArrayList<ArrayList<Integer>> arrays=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> array=new ArrayList<Integer>();
        if(root==null)return arrays;
        queue.offer(root);
       // array.add(root.val); 如何进行表示表示他们是在同一层 是个问题的关键所在  可以利用for循环来实现判断是否还存在数据供我们访问，是一个经典所在。
        while(queue.size()!=0){
            int len=queue.size();          
            for(int i=0;i<len;i++){
                 TreeNode temp=queue.poll();
            if(temp.left!=null){
                queue.add(temp.left);
            }
            if(temp.right!=null){
                queue.add(temp.right);
            }
                array.add(temp.val);
            }
            arrays.add(array);
             array=new ArrayList<Integer>();
        }
        return arrays;
    }
}

变形讲解

102-Binary Tree Level Order Traversal

实现效果如下：

思路：自是对于层序遍历的一个小小的变形，在最开始的所有的遍历中，输出的都是一个**（ArrayList）链表**。但是此时我们需要输入的不再是简简单单的链表，而是以数组为泛型的数组。这里需要进行讲解一下：我们可以先行创建一个数组，由于存放的是每一行的元素，这个不难实现，下面，我们需要做到的是，将这每一行的数组再加入到以一个数组为泛型的数组中。让我举个栗子：
栗子：
如下所示，在进行泛型数组的添加时候，对于相同名字的数组在添加时候会进行覆盖的情况，所以完成一次对以数组为泛型的数组的add以后，要对数组类型进行一次新的new（创建一个全新的对象，再次进行添加操作）

 @Test
    public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> arrayLists=new ArrayList<ArrayList<Integer>>();
        arrayList.add(1);
        arrayList.add(2);
        System.out.println(arrayList);
        arrayLists.add(arrayList);
        System.out.println(arrayLists);
        arrayList=new ArrayList<>();
        arrayList.add(3);
        arrayList.add(4);
        System.out.println(arrayList);
        arrayLists.add(arrayList);
        System.out.println(arrayLists);
        }

打印结果如下：

[1, 2]
[[1, 2]]
[3, 4]
[[1, 2], [3, 4]]

代码：

class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int level = 0;
    while ( !queue.isEmpty() ) {
      levels.add(new ArrayList<Integer>());
      int level_length = queue.size();
      for(int i = 0; i < level_length; ++i) {
        TreeNode node = queue.remove();
        levels.get(level).add(node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
        }
      level++;
    }
    return levels;
  }
}

100- same-tree

思路：判断一个数是否完全和另外一个数是相等的，也是要不断得实现对数的遍历。下面提供两种方法解决。

递归：重点是不同情况的判断

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return firstList(p,q);
          }
    private boolean firstList(TreeNode root1,TreeNode root2){
       if(root1==null &&root2==null)
            return true;
        if(root1==null || root2==null)
            return false;
        if(root1.val!=root2.val)
            return false;
        return firstList(root1.left,root2.left)&&firstList(root1.right,root2.right);
    }
}

迭代：重点是对栈的利用+各种不成立情况判断。

import java.util.*;
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(p);
        stack.push(q);
        while(!stack.isEmpty()){
             p=stack.pop();
             q=stack.pop();
            if(p==null && q==null) continue;
            if(p==null || q==null) return false;
            if(p.val!= q.val) return false;
            stack.push(p.left);
            stack.push(q.left);
            stack.push(p.right);
            stack.push(q.right);
        }
        return true;
}
}

110 Balance-binary-tree

判断给定的一个二叉树是不是平衡二叉树;
平衡二叉树：每一个结点的左右两个子树的高度差不超过1.
思路: 对于这种问题，之前我们也讲过试想一下，判断这种问题的关键在于得出一个二叉树的左右节点的高度，然后进行判断最高的高度减去最低的高度的值是否是大于1的，那么如何得到一棵二叉树的高度，此时就可以使用到递归的算法，不断递归进入左右子树，对其的高度加一，再使用一个max函数和min函数进行减法运行即可。

public class Solution {
    boolean flag=false;
    public boolean isBalanced(TreeNode root) {
        depth(root);
        return !flag;
    }
    private int depth(TreeNode t){
        if(flag ||t==null)
            return 0;
        int left=depth(t.left);
        int right=depth(t.right);
        if(Math.max(left,right)-Math.min(left,right)>1)
        {
            flag=true;
        }
        return 1+Math.max(left,right);
    }
}

114 Flatten Binary Tree to Linked List

将一个二叉树转换成为一个链表类型的二叉树（要求使用原地转换）

思路： 其实这道题目可以使用最基础的先序遍历来解决，每一次先序遍历的层次都是从左到右的输出，这个时候将其接在右子树上即可，但是这里有一个小小的问题，对于c++来说栈的操作有一个 top() 函数可以实现对栈顶元素进行访问。但是对于java并没有这个函数，所以想要使用这个方法时候，还需要再度创建多于的栈用来存放已经遍历出来的元素，再次存放到里面，就是多于的空间消耗。于是就有了一下的解法，思路也是比较简单。

public void flatten(TreeNode root) {
    while (root != null) { 
        //左子树为 null，直接考虑下一个节点
        if (root.left == null) {
            root = root.right;
        } else {
            // 找左子树最右边的节点
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            } 
            //将原来的右子树接到左子树的最右边节点
            pre.right = root.right;
            // 将左子树插入到右子树的地方
            root.right = root.left;
            root.left = null;
            // 考虑下一个节点
            root = root.right;
        }
    }
}

117-Populating Next Right Pointers in Each Node II

思路 ：这个题目有使用到 pummy指针，在这个题目之前，还有一个是完全二叉树，这里不再展示出来，使用简单的递归，还是比较容易实现的。但是对于不是完全二叉树的实现，可能就需要用到不同的思想。这里的pummy指针就是比较好的思想：一个空节点在开始时候指向当前层，定义一个pre前驱指针指向当前层的下一层，进行操作，在完成以后，此时的dummy指针的next指针已经发生了变化，指向了当前层的下一次，此时再次开始新一轮的操作，于此往复。
代码：

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null) 
            return;
        TreeLinkNode node=new TreeLinkNode (0);
        TreeLinkNode cur;
        TreeLinkNode pre=node;
        for(cur=root;cur!=null;cur=cur.next){
            if(cur.left!=null){
                pre.next=cur.left;
                pre=pre.next;
            }
             if(cur.right!=null){
                pre.next=cur.right;
                pre=pre.next;
            }
        }
        connect(node.next);
    }
}

结语: 以上就是关于在遍历阶段所出现的一些算法题目，或多或少都有一些遍历的影子。写这一系列博客的主要原因是，觉得泛泛的刷力扣不能达到总结的效果，打算把系列的题目总结起来，也方便在以后面试的复习中，能够很快找到要点。