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

Example:

Input: [1,null,2,3]   1    \     2    /   3Output: [1,3,2]

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

 

思路

---

　　这道题考察的是二叉树的中序遍历，中序遍历的解法有两种，一种是使用递归，一种是使用循环来解决。下面附上两种解法的代码。

解决代码

---

　　递归解决代码　

1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.left = None 6 #         self.right = None 7  8 class Solution(object): 9     def inorderTraversal(self, root):10         """11         :type root: TreeNode12         :rtype: List[int]13         """14         if not root:   # 空节点直接返回15             return []16         res  =[]17         self.indorder(root, res)     # 中序遍历18         return res19     20     def indorder(self, root, res):    # 中序遍历函数21         if not root:22             return23         24         self.indorder(root.left, res)25         res.append(root.val)26         self.indorder(root.right, res)

 

　　循环解决代码(循环主要是使用栈来解决)

1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.left = None 6 #         self.right = None 7  8 class Solution(object): 9     def inorderTraversal(self, root):   14         if not root:15             return []16         res = []      #   记录结果列表17         stack = []18         while stack or root:    # 循环条件19             if root:               # 中序遍历，需要先将左边节点遍历完毕。20                 stack.append(root)21                 root = root.left22             else:                # 意味左节点为空，这时进行弹出。并遍历弹出节点的右子树。23                 root = stack.pop()24                 res.append(root.val)25                 root = root.right26         return res