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代码：

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)