leetcode - 94. 二叉树的中序遍历

94. 二叉树的中序遍历

        List<Integer> inorder = new ArrayList<>();
        
        public List<Integer> inorderTraversal(TreeNode root) {
            withStack(root);
            return inorder;
        }

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

        //迭代
        public void withStack(TreeNode root) {
            if(root == null){
                return;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode cur = root;
            while(cur != null || !stack.isEmpty()){
                //不断往左子树方向走，每走一次就将当前节点保存到栈中
                //这是模拟递归的调用
                if(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                //当前节点为空，说明左边走到头了，从栈中弹出节点并保存
                //然后转向右边节点，继续上面整个过程
                }else{
                    TreeNode pop = stack.pop();
                    inorder.add(pop.val);
                    cur = pop.right;
                }
            }
        }