leetcode_【94】二叉树的中序遍历

1.题目描述

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

示例:

> 输入: [1,null,2,3]
>        1
>         \
>          2
>         /
>        3
> 输出: [1,3,2]
> 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
>

2.解题思路

思路1：使用递归

中序遍历的 左子树--> 跟--> 右子树

思路2：迭代

用一个指针模拟访问过程，先遍历到root的最左节点，

>              1
>            /    \
>           2      3
>         /  \    / 
>        4    5  6
> (1)第一次循环，栈stack里面放入root的左子树：分别放入1--2--4为root的树，然后ans里面存入stack.pop(),即4，cur = cur.right = null
> (2)stack内有2个TreeNode,进入第二次循环，ans.add(cur.val) = 2;cur = cur.right = 5;
> (3)stack里面还有一个以1为root的TreeNode,进入第三次循环，stack加入以5为root的TreeNode,ans加入5，cur = null,
> (4)stack里面还有一个以1为root的TreeNode,进入第四次循环，ans加入1，cur = cur.right = 3
> (5)cur!=null,进入第四次循环,stack加入3和6为root的树，ans加入6，cur = null
> (6) stack里面还有一个以3为root的TreeNode,进入第五次循环，ans加入3，cur = null,stack为空，结束循环
>

3.代码

方法1：递归

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

方法2：迭代

public static List<Integer> inorderTraversal2(TreeNode root) {
          List<Integer> ans = new ArrayList<>();
          Stack<TreeNode> stack = new Stack<>();
          TreeNode cur = root;
          while (cur!=null ||!stack.isEmpty()){
              while (cur!=null){
                  stack.push(cur);
                  cur = cur.left;
              }
              cur = stack.pop();
              ans.add(cur.val);
              cur = cur.right;
          }
          return ans;
      }

4.提交结果