二叉树的遍历：先序遍历，中序遍历，后序遍历（java）

来源：力扣（LeetCode）
链接：144.前序遍历、94.中序遍历、145.后序遍历

概念：

首先，我们结合图形了解一下他们的原理
前序遍历：即先序遍历(Pre-order)，指按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。

中序遍历：中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。巧记：左根右。

后序遍历：后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。巧记：左右根。

三个题目了解套路~
——————————
这是个可爱的分割线……
——————————

先序遍历

题目

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

输入: [1,null,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 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res){
        if(root == null) return ;
        res.add(root.val);//每次访问，节点放进来
        helper(root.left, res);//找左子树
        helper(root.right, res);//找右子树
    }
}

二、迭代：
看一下原理图：
注意：栈中的元素是先进后出

/**
 * 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> res = new LinkedList<>();
    if (root == null) {
      return res;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode t = stack.pop();//删除并记录栈顶元素
      res.add(t.val);
      if (t.right != null) {
        stack.push(t.right);//放入右节点
      }
      if (t.left != null) {
        stack.push(t.left);//放入左节点
      }
    }
    return res;
  }
}

——————————
这是个高冷的分割线……
——————————

中序遍历

题目

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

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

输出: [1,3,2]

》请问是中序遍历吗？
——是的
》好的，左根右(^ V ^) y

必杀技一：递归

/**
 * 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> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res){
        if(root == null) return ;
        helper(root.left, res);//遇到结点，先找他的左子树，直到左子树触底了（报告：发现叶子结点
        res.add(root.val);//加进来
        helper(root.right, res);/同理访问右子树
    }
}

必杀技二：迭代
先看看图：

突然进栈出栈的好像挺突兀的，不需要想得太复杂，我们已经掌握了原理“左根右”，不要怕——
简单说一下：当我们遇到一个结点时，一直去找它的左子树，直到左子树为空了，那么就可以把当前节点记录了，然后去访问右子树，对待右子树也是如此，去找它的左子树……

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
      return res;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode t = stack.pop();
      res.add(t.val);
      if (t.right != null) {
        stack.push(t.right);
      }
      if (t.left != null) {
        stack.push(t.left);
      }
    }
    return res;
  }
}

——————————
这是个高冷的分割线……
——————————

后序遍历

题目

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

输入: [1,null,2,3]
输出: [3,2,1]

碰到后序遍历~
老套路了，我又懂了(不是 （^ V ^）

递归：

/**
 * 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> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res){
        if(root == null) return;
        helper(root.left, res);//左子树
        helper(root.right, res);//右子树
        res.add(root.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> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
      return res;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();//取出栈顶元素
      res.addFirst(node.val);//每次都放到首位，实现对称
      if (node.left != null) {//左节点入栈
        stack.push(node.left);
      }
      if (node.right != null) {//右节点入栈
        stack.push(node.right);
      }
    }
    return res;
  }
}

——————————
未完待续……
——————————