二叉树的中序遍历

94. 二叉树的中序遍历

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

代码

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        // inorder01(root);
        // inorder02(root);
        inorder03(root);
        return list;
    }
    

    //递归
    public void inorder01(TreeNode root){
        if(root==null) return;
        inorder01(root.left);
        list.add(root.val);
        inorder01(root.right);
    }


    //迭代
    public void inorder02(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> st = new Stack<>();
        while(root!=null||!st.isEmpty()){
             while(root!=null){
                st.push(root);
                root = root.left;
             }
             root = st.pop();
             list.add(root.val);
             root = root.right;
         }
    }

    //迭代标记法
    public void inorder03(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.pop();
            if(node!=null){
                if(node.right!=null) st.push(node.right); //右
                st.push(node);//中
                st.push(null);//标记
                if(node.left!=null) st.push(node.left); //左
            }else{
                node = st.pop();
                list.add(node.val);
            }
        }
    }
}