94_二叉树的中序遍历
@
描述给定一个二叉树，返回它的中序遍历。
示例：
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]进阶： 递归算法很简单，你可以通过迭代算法完成吗？
方法一：递归 Java 代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<>(); inorderTraversal(root, ret); return ret; } private void inorderTraversal(TreeNode root, List<Integer> ret) { if (root == null) { return; } inorderTraversal(root.left, ret); ret.add(root.val); inorderTraversal(root.right, ret); } }复杂度分析：
时间复杂度：\(O(n)\)，其中，\(n\) 为二叉树节点的数目
空间复杂度：平均为 \(O(log(n))\)，最坏的情况为 \(O(n)\)
Python代码 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ def dfs(root, ret): if root is None: return dfs(root.left, ret) ret.append(root.val) dfs(root.right, ret) ret = list() dfs(root, ret) return ret复杂度分析同上。
方法二：非递归 Java 代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); ret.add(cur.val); cur = cur.right; } return ret; } }复杂度分析：
时间复杂度：\(O(n)\)，其中，\(n\) 为二叉树节点的数目
空间复杂度：\(O(h)\)，其中，\(h\) 为二叉树的高度
Python 代码 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ret, stack = [], [] cur = root while cur is not None or len(stack) > 0: while cur is not None: stack.append(cur) cur = cur.left cur = stack.pop() ret.append(cur.val) cur = cur.right return ret复杂度分析同上。