题解 | #二叉树的中序遍历#

递归

思路：递归方法比较简单

• 第一步：判断左子树若不为空，遍历左子树
• 第二步：添加根节点值
• 第三步：判断右子树若不为空，遍历右子树

import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
        //特殊情况 
        if(root==null)return new int[0];
      
        List<Integer> list=new ArrayList<>();
        //调用递归方法
        center(list,root);
        int[] res = new int[list.size()];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        return res;
    }
    //递归方法
    public void center(List<Integer> list,TreeNode t){
      
        if(t.left!=null)center(list,t.left);
        list.add(t.val);
        if(t.right!=null)center(list,t.right);
        
    }
}

非递归

思路：中序遍历要求先遍历左子树

• 第一轮循环：从根节点开始，判断如果有左子树，然后压入栈
• 第二轮循环：出栈，判断出栈节点是否有右子树，有的话入栈，此处套循环，如果这个右子树有左子树的话，也像第一轮循环，逐个入栈

注意： 非递归方法可以使用do-while循环简化

import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        Stack<TreeNode> s=new Stack<>();
        List<Integer> list=new ArrayList<>();
        
        TreeNode p=root;
        //第一轮循环，左子树压入栈
        while(p!=null){
            s.push(p);
            p=p.left;
        }
        //第二轮循环，出栈，并判断是否有右子树
        while(!s.empty()){
            p=s.pop();
            list.add(p.val);
            //判断右子树不为空的情况
            if(p.right!=null){
                p=p.right;
                //套循环，左子树入栈
                while(p!=null){
                    s.push(p);
                    p=p.left;
                }
            }
        }
        
        int[] res=new int[list.size()];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        
        return res;
    }
}