#94 Binary Tree Inorder Traversal——Top 100 Liked Questions

本文主要是介绍#94 Binary Tree Inorder Traversal——Top 100 Liked Questions，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]1\2/3Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

第一次：递归实现（https://blog.csdn.net/monster_ii/article/details/82115772）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []res = []res += self.inorderTraversal(root.left)res.append(root.val)res += self.inorderTraversal(root.right)return res

Runtime: 16 ms, faster than 94.53% of Python online submissions for Binary Tree Inorder Traversal.

Memory Usage: 11.9 MB, less than 24.93% of Python online submissions for Binary Tree Inorder Traversal.

 第二次：迭代：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res, stack = [], []while True:while root:stack.append(root)root = root.leftif not stack:return resnode = stack.pop()res.append(node.val)root = node.right

Runtime: 12 ms, faster than 98.48% of Python online submissions for Binary Tree Inorder Traversal.

Memory Usage: 11.8 MB, less than 29.40% of Python online submissions for Binary Tree Inorder Traversal.

这篇关于#94 Binary Tree Inorder Traversal——Top 100 Liked Questions的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---