中序遍历

问题陈述

实现二叉树的中序遍历

问题解决

1、递归法

根据中序遍历“左根右”的特点，编写代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
    public List<Integer> inorderTravelsal(TreeNode root){
        List<Integer> list=new ArrayList<>();
        dfs(list,root);
        return list;
    }
    public void dfs(List<Integer> list,TreeNode root){
        if(root==null) return null;
        dfs(list,root.left);
        list.add(root.val);
        dfs(list,root.right);
    }
}

2、迭代法（基于栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    public List<Integer> inorderTravelsal(TreeNode root){
        List<Integer> list=new ArrayList<>();
        Stack<Integer> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            list.add(cur.val);
            cur=cur.right;
        }
       return list;
    }
    
}