题目

给定一个二叉树的根节点 root ，返回它的 中序 遍历

示例

image.png
输入：root = [1,null,2,3]
输出：[1,3,2]

输入：root = []
输出：[]

输入：root = [1]
输出：[1]

image.png
输入：root = [1,2]
输出：[2,1]

image.png
输入：root = [1,null,2]
输出：[1,2]

解题思路——递归

  1. 中序遍历的逻辑是：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树；
  2. 递归结束的标志是：当结点为空，结束递归。
  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class Binary_Tree_Inorder_Traversal_94 {
  6.     public class TreeNode {
  7.       int val;
  8.       TreeNode left;
  9.       TreeNode right;
  10.       TreeNode() {}
  11.       TreeNode(int val) { this.val = val; }
  12.       TreeNode(int val, TreeNode left, TreeNode right) {
  13.           this.val = val;
  14.           this.left = left;
  15.           this.right = right;
  16.       }
  17.     }
  19.     public List<Integer> inorderTraversal(TreeNode root) {
  20.         List<Integer> res = new ArrayList<Integer>();
  21.         centre(root,res);
  22.         return res;
  23.     }
  25.     public void centre(TreeNode root, List<Integer> res){
  26.         if(root == null){
  27.             return;
  28.         }
  29.         centre(root.left,res);
  30.         res.add(root.val);
  31.         centre(root.right,res);
  32.     }
  33. }

解题思路——迭代（栈）

  1. 中序遍历的逻辑是：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树；
  2. 在结点不为空或者栈不为空（要栈不为空原因是：到最底下的结点的左孩子，它为空，直接停止了遍历）的情况下遍历：当结点不为空，则进栈，然后遍历左孩子结点；当结点为空，则出栈，将结果保存到列表中，然后遍历右孩子结点。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Binary_Tree_Inorder_Traversal_94 {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> sk = new Stack<TreeNode>();
        while(root != null || !sk.empty()){
            if (root != null){
                sk.push(root);
                root = root.left;
            }else{
                root = sk.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}