题目描述

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

示例：

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

输出: [1,3,2]

递归求解思路

1.经典递归，左->根->右递归即可。

Java代码实现

    private List<Integer> res = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root != null){
            inorderTraversal(root.left);
            res.add(root.val);
            inorderTraversal(root.right);
        }
        return res;
    }

迭代法求解思路

  1. 借助栈来处理节点的先后顺序即可。

Java代码实现

   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();

        while(root != null || !stack.empty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }