给你二叉树的根节点 root ，返回它节点值的中序遍历

**二叉树的中序遍历**

在计算机科学中，二叉树是一种常见的数据结构，它由一系列结点组成，每个结点最多有两个子结点：左孩子和右孩子。二叉树的中序遍历是指按照从最小值到最大值的顺序访问每个结点。

**定义**

给定一个二叉树的根节点 `root`，返回它节点值的中序遍历。

**示例**

例如，我们有如下二叉树：

4 / 
25 /  
136

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef inorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 res = []
 if not root:
 return res # 递归左子树 left_res = inorderTraversal(root.left)
 # 中序遍历当前结点 res.append(root.val)
 # 递归右子树 right_res = inorderTraversal(root.right)
 return left_res + res + right_res# 测试用例root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(6)

print(inorderTraversal(root)) # [1,2,3,4,5,6]

def inorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 res = []
 stack = []
 while True:
 # 进入左子树 while root:
 stack.append(root)
 root = root.left # 中序遍历当前结点 if not stack:
 return res node = stack.pop()
 res.append(node.val)
 # 进入右子树 root = node.right return res# 测试用例root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(6)

print(inorderTraversal(root)) # [1,2,3,4,5,6]