中序遍历二叉树

题目：

• 给定一个二叉树的根节点root，返回它的中序遍历结果

示例.png

解法：

• 第一种方法（递归）：中序遍历是指：左子树—根节点—右子树，可以定义一个中序遍历的函数，然后递归调用

 class Solution {
 public List<Integer> inorderTraversal(TreeNode root) {
 List<Integer> res=new ArrayList<>();
 inorder(root,res);//调用递归的方法
 return res;

 }
 public static void inorder(TreeNode root,List<Integer> res){
 if(root==null){//如果传进来的根节点为空，说明这是空树
 return;
 }
 inorder(root.left,res);//遍历左子树
 res.add(root.val);//遍历完左子树后，将根节点添加到数组中
 inorder(root.right,res);//遍历右子树
 }
 }
 时间复杂度为O(n)需要遍历二叉树的所有结点
 空间复杂度为O(n)递归调用需要用到栈先来存储元素

• 第二种方法（迭代）：跟第一种方法等价，迭代是把栈模拟出来

class Solution {  public List<Integer> inorderTraversal(TreeNode root) {  

List<Integer> res=new ArrayList<>();

Stack<TreeNode> stk=new Stack<>();//创建一个栈

 while(root!=null||!stk.isEmpty()){
 while(root!=null){
 stk.push(root);
 root=root.left;//遍历左子树，然后将节点进栈
 }
 root=stk.pop();//左子树为空，然后将栈顶元素出栈为当前节点
 res.add(root.val);
 root=root.right;//遍历当前节点的右子树
 }
 return res;
 }


}