NC161 二叉树的中序遍历

NC161 二叉树的中序遍历

二叉树的中序遍历_牛客题霸_牛客网 (nowcoder.com)

94. 二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

// //递归
// import java.util.*;
// public class Solution {
//     public void inorder(TreeNode root,List<Integer> list){
//         if(root==null){
//             return;
//         }
//         inorder(root.left,list);
//         list.add(root.val);
//         inorder(root.right,list);
//     }
//     public int[] inorderTraversal (TreeNode root) {
//         List<Integer> list=new ArrayList<>();
//         inorder(root,list);
//         //
//         int[] ret=new int[list.size()];
//         for(int i=0;i<list.size();i++){
//             ret[i]=list.get(i);
//         }
//         return ret;
//     }
// }


//中序遍历-左根右
//迭代
import java.util.*;
public class Solution {
    public int[] inorderTraversal (TreeNode root) {
        if(root==null){
            return new int[0];
        }
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> st=new Stack<TreeNode>();
        TreeNode cur=root;
        while(cur!=null||st.isEmpty()==false){
            while(cur!=null){
                st.push(cur);
                cur=cur.left;
            }
            cur=st.pop();
            list.add(cur.val);
            cur=cur.right;
        }
        //
        int[] ret=new int[list.size()];
        for(int i=0;i<list.size();i++){
            ret[i]=list.get(i);
        }
        return ret;
    }
}