35.Binary Tree Inorder Traversal-二叉树的中序遍历

解析：递归和非递归

 class Solution {
     List<Integer> res = new ArrayList<>();
     public List<Integer> inorderTraversal(TreeNode root) {
         /**
             * 递归
             */
         //        if(root==null){
         //            return new ArrayList<>();
         //        }
         //        inorderTraversal(root.left);
         //        res.add(root.val);
         //        inorderTraversal(root.right);
         //        return res;
         /**
             * 非递归  压栈
             * 先全部压左，再压右
             */
         Stack<TreeNode> stack = new Stack<>();
         if (root == null) return new ArrayList<>();
         //压左孩子节点
         while (root != null || !stack.isEmpty()) {
             if (root != null) {
                 stack.push(root);
                 root = root.left;
             } else {
                 TreeNode currRoot = stack.pop();
                 res.add(currRoot.val);
                 root = currRoot.right;
             }
         }
         return res;
     }
}