package cn.jiedada.controller;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 数的中序遍历
 */
class Solution {
    public List< Integer > inorderTraversal(TreeNode root) {
        //定义两个参数
        List < Integer > res = new ArrayList< >();
        Stack< TreeNode > stack = new Stack < > ();
        //如果节点不为null或者stack里面还有节点就进行循环
        while ( root!=null || stack != null){
            //获得所有坐儿子入stack
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            //当没有左儿子的时候就需要出stack
            root = stack.pop();
            res.add(root.val);
            //最后走右儿子
            root = root.right;
        }
        return res;
    }
}