leetcode 94 二叉树的中序遍历

理解中序遍历关键在于左---根---右的顺序，

也就是说递归访问左子树，到null为止

然后递归栈弹出

在这个时候访问节点就会满足 左根右的顺序

其他的几种遍历，比如前序遍历 根左右

实际也一样，这时候就要先访问根节点，然后递归左，再递归右。

ArrayList res = new ArrayList<> ();
    public void addData(TreeNode root){
        //如果是个空树；直接返回[]
        if(root == null)
            return;
        // 按照左根右的顺序

        addData (root.left);
        //代码执行到这里的时候，就说明左子树已经遍历完了；
        res.add (root.val);
        addData (root.right);
    }
    public List inorderTraversal(TreeNode root) {
        addData(root);
       return res;

    }

还有一种是非递归遍历

实际是用栈模拟了递归

ArrayList res = new ArrayList<> ();

public List inorderTraversal(TreeNode root) {
        Stack stree = new Stack<> ();
        if (root == null) {
            return res;
        }
        //确保遍历已经结束的两个条件
        //一个是当前节点是空节点，还有就是栈空
       //如果当前节点是空节点，但是栈不空，说明节点还没遍历完
       //如果当前节点不为空，但是栈空，，说明节点没入栈
       //两个条件都要满足 
        while (root != null ||!stree.isEmpty ()){
            
            //先遍历左节点  
            while (root != null) {
                stree.push (root);
                root = root.left;
            }
             //左节点遍历结束
            TreeNode topNode = stree.pop ();
            res.add (topNode.val);
            //再看右节点    
            root = root.right;
        }
        return res;

    }