作者：因情语写

链接：https://www.proprogrammar.com/article/614

声明：请尊重原作者的劳动，如需转载请注明出处

    在上节的介绍中，相信大家已经熟知了树和二叉树的基本概念。

    本章节，我们把重点放在介绍二叉树中几种常见的遍历方法。掌握这几种遍历方法，会加深你对树这个数据结构的理解，并为以后的学习打下扎实的基础。

    本章目标：

1. 理解和区分树的遍历方法
2. 能够运用递归方法解决树的为前序遍历、中序遍历和后序遍历问题
3. 能用运用迭代方法解决树的为前序遍历、中序遍历和后序遍历问题
4. 能用运用广度优先搜索解决树的层序遍历问题

 树的遍历 - 介绍

• 前序遍历
• 中序遍历
• 后序遍历
• 递归和迭代

    前序遍历

    前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

    请看下面的例子：

    中序遍历

    中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

    让我们一起来看树的中序遍历：

    通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。 我们将在另一张卡片（数据结构介绍 – 二叉搜索树）中再次提及。

    后序遍历

    后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

    我们一起来看后序遍历的动画演示：

    值得注意的是，当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。 也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。

    另外，后序在数学表达中被广泛使用。 编写程序来解析后缀表示法更为容易。 这里是一个例子：

    您可以使用中序遍历轻松找出原始表达式。 但是程序处理这个表达式时并不容易，因为你必须检查操作的优先级。

    如果你想对这棵树进行后序遍历，使用栈来处理表达式会变得更加容易。 每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中。

    递归和迭代

    请练习文章后面习题中的三种遍历方法。 您可以通过递归或迭代方法实现算法，并比较它们之间的差异。

    算法-二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        result.clear();
        preorder(root);
        return result;
    }
    
    private void preorder(TreeNode node) {
        if(null != node){
            result.add(node.val);
            preorder(node.left);
            preorder(node.right);
        }
    }
}

    上面是递归的方法，下面看一下非递归的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.add(node.val);
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }
}

    非递归栈，先进右子树，再进左子树，这样出时先出左子树，再出右子树

    算法-中序遍历二叉树

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
}
    
public void inorder(TreeNode node, List<Integer> result){
    if(node != null){
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
   }
}

     上面是递归的方法，再看一下非递归的方法

// 用栈，非递归
    // 处理树：对一个节点，如果有左孩子且没被处理过，入栈，然后处理最左没被处理的那个节点，如果此节点有右孩子，右孩子入栈
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        List<TreeNode> visited = new ArrayList<>();
        TreeNode temp, left;
        
        if(root == null){
            return result;
        }
        
        stack.push(root);

        while(!stack.isEmpty()){
            temp = stack.peek();
            while(temp.left != null && !visited.contains(temp.left)){
                stack.push(temp.left);
                temp = temp.left;
            }

            result.add(temp.val);
            visited.add(temp);
            stack.pop();

            if(null != temp.right){
                stack.push(temp.right);
            }
        }
        
        return result;
    }

    处理结点的顺序：对一个节点，如果有左孩子且没被处理过，入栈，然后处理最左没被处理的那个节点，如果此节点有右孩子，右孩子入栈

    算法-二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

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

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    private void postorder(TreeNode node, List<Integer> result) {
        if(node != null){
            postorder(node.left, result);
            postorder(node.right, result);
            result.add(node.val);
        }
    }
}

    上面是递归的方法，下面再看一下非递归的方法

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

    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    private void postorder(TreeNode node, List<Integer> result) {
        if(node != null){
            postorder(node.left, result);
            postorder(node.right, result);
            result.add(node.val);
        }
    }
    
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        List<TreeNode> visited = new ArrayList<>();

        if (root == null) {
          return result;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
              TreeNode node = stack.peek();

              while (node.left != null && !visited.contains(node.left)) {
                  stack.push(node.left);
                  node = node.left;
              }
            
            if(node.right != null && !visited.contains(node.right)){
                stack.push(node.right);
            }else{
                stack.pop();
                result.add(node.val);
                visited.add(node);
                
            }
        }
        return result;
    }
}

    和先序遍历的非递归方法类似，要用到标记

    层序遍历 - 介绍

    层序遍历就是逐层遍历树结构。

    广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

    当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。

    这是一个层序顺序遍历的例子：

    通常，我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索。 如果您对队列不熟悉，可以在我们即将推出的另一张卡片中找到更多有关信息。

亲爱的读者：有时间可以点赞评论一下