题目描述

题目链接:94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

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

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

递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    public void inorder(TreeNode root, List<Integer> list){
        if(null != root){
            //递归左子树
            inorder(root.left, list);
            //访问根节点
            list.add(root.val);
            //递归右子树
            inorder(root.right, list);
        }
    }
}

迭代

1. 先遍历到当前结点，但不求值，入栈
2. 接着遍历左结点，入栈，往下遍历
3. 当前结点没有左结点了，则出栈，求值
4. 当前结点有右结点，重复步骤1
5. 遍历直到栈为空为止

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        //初始化一个栈
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(null != cur || !stack.isEmpty()){
            while(null != cur){
                stack.push(cur);
                //不断压入左子树
                cur = cur.left;
            }
            //栈顶节点出栈
            cur = stack.pop();
            //取值
            res.add(cur.val);
            //压入右子树
            cur = cur.right;
        }
        return res;
    }
}