LeetCode 94 Binary Tree Inorder Traversal

LeetCode

<div class="_1l1MA">

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

Example 1:

<pre>Input: root = [1,null,2,3] Output: [1,3,2] </pre>

Example 2:

<pre>Input: root = [] Output: [] </pre>

Example 3:

<pre>Input: root = [1] Output: [1] </pre>

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?</div>

题目大意：

求树的中序遍历

解题思路：

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)