二叉树的中序遍历（94），

二叉树的中序遍历（94），

题目描述：给定一个二叉树，返回它的中序 遍历。
示例:
　　输入: [1,null,2,3]
 　　  　　1
  　　　　  \
  　　　　   2
 　　　　   /
　　　　   3
输出: [1,3,2]

 

解法一：递归（较简单）　　　　

/**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution {     List<Integer> lis = new ArrayList<>();      public List<Integer> inorderTraversal(TreeNode root) {         if(root == null)    return lis;　　//若节点为空，则返回当前结果数组         inorderTraversal(root.left);　　　 //对左子树进行中序遍历         lis.add(root.val);　　　　　　　　　　         inorderTraversal(root.right);　　　//对右子树进行中序遍历         return lis;     } }   解法二：（迭代）--基于栈的中序遍历 class Solution {         public List<Integer> inorderTraversal(TreeNode root) {             List<Integer> list = new ArrayList<>();             Stack<TreeNode> stack = new Stack<>();             TreeNode cur = root;             while (cur != null || !stack.isEmpty()) {                 if (cur != null) {                     stack.push(cur);//保留当前根节点信息                     cur = cur.left;                 } else {                     cur = stack.pop();                     list.add(cur.val);                     cur = cur.right;                 }             }             return list;         }     }