KK's blog

每天积累多一些

0%

LeetCode 94 Binary Tree Inorder Traversal

LeetCode



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

Example 1:



Input: root = [1,null,2,3]
Output: [1,3,2]


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [1]
Output: [1]


Constraints:

The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

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

题目大意:

求树的中序遍历

解题思路:

DFS

解题步骤:

N/A

注意事项:

N/A

Python代码:

1
2
3
4
5
6
7
def inorderTraversal(self, root: TreeNode) -> List[int]:
return self.dfs(root)

def dfs(self, root):
if not root:
return []
return self.dfs(root.left) + [root.val] + self.dfs(root.right)

算法分析:

时间复杂度为O(n),空间复杂度O(1)

Free mock interview