目录

一、题目

二、示例

三、思路

四、代码

一、题目

给定一个二叉树，返回它的中序遍历。

二、示例

示例:

输入: [1,null,2,3]1\2/3输出: [1,3,2]

三、思路

1、递归。后序遍历：左-->根-->右。

2、非递归，栈的思想，先进后出。

四、代码

1、

# Definition for a binary tree node.
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution: def inorderTraversal(self, root: TreeNode):if root is None:return []return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)if __name__ == '__main__':root = TreeNode(1)root.left = Noneroot.right = TreeNode(2)root.right.left = TreeNode(3)s = Solution()ans = s.inorderTraversal(root)print(ans)

2、

# Definition for a binary tree node.
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution: def inorderTraversal(self, root: TreeNode):res = []if root is None:return resstack = []while stack or root:if root is not None:stack.append(root)root = root.leftelse:root = stack.pop()res.append(root.val)root = root.rightreturn resif __name__ == '__main__':root = TreeNode(1)root.left = Noneroot.right = TreeNode(2)root.right.left = TreeNode(3)s = Solution()ans = s.inorderTraversal(root)print(ans)