leetcode 94 二叉树的中序遍历 递归和迭代

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3] 1 2 / 3

输出: [1,3,2] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

迭代

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while(curr!=null || !stack.isEmpty()){ while(curr!=null){ stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; } }

递归

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root,res); return res; } public void inorder(TreeNode root,List<Integer> res){ if(root==null){ return ; } inorder(root.left,res); res.add(root.val); inorder(root.right,res); } }