2020-05-27【】

调试程序的时候，需要准备测试数据

左节点为空：[1,null,2,3]
        1
null        2
        3

右节点为空：[2,3,null,1]
              2
        3
null       1

规则：左根 右

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> data=new ArrayList<>();
        if(root==null){
            return data;
        }
        Stack < TreeNode > stack = new Stack < > ();
        stack.push(root);
        while(!stack.isEmpty()){
            while(root.left!=null && root!=null){
                stack.push(root.left);
                root=root.left;
            }
            root=stack.pop();
            data.add(root.val);
            if(root.right!=null){
                stack.push(root.right);
                root=root.right;
            }
        }
        return data;

    }

解析：

先把2压入  然后判断2的左节点3 不是空 2也不是空  就把3压入  此时光标指向3
然后判断 3的 左节点 1 以及 3  都不是空 就把1 压入  此时 光标指向1
但是 1的左节点为空，就把栈顶元素 1 弹出来
判断 1的右边节点为空。继续执行while(!stack.isEmpty())
但是 1 的左边节点为空  继续出栈，  此时 3 出栈
3的 右边节点也为空
继续执行while(!stack.isEmpty())  循环 
【但是 此时 3的左边节点 1不是空 3也不是空
就出现把已经出栈的1 继续入站的情况了】
然后光标又到1了，接下来就是弹出1  最后弹出2
变成了  1 3 1 2的局面了。
正确的顺序应该是 1 3 2