中序遍历
2019-07-15 本文已影响0人
hustyanye
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/
中序遍历的递归实现还是很容易的,自己在函数里面写过help,再递归去调用即可
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
arr = []
def help(root):
if not root:
return
help(root.left)
arr.append(root.val)
help(root.right)
help(root)
return arr
非递归调用的时候,需要自己用一个队列模拟递归操作
先找到最左的节点,不停的push到队列中,然后取出队列末端元素输出,在遍历其右子树即可
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
arr = []
queue = []
tmp = root
while tmp or queue:
while tmp:
queue.append(tmp)
tmp = tmp.left
last = queue.pop()
arr.append(last.val)
tmp = last.right
return arr