中序遍历

中序遍历

九月 02, 2021

中序遍历

这道题在看了好多个视频以后终于大概理解了em

第一种方法是用递归的方法

分别对应三种遍历

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

递归的时候终止条件便是当前节点root为空的时候

而中序遍历递归时则先尝试调用左节点 再打印当前根节点 再调用右节点就可

所以代码如下

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def inorderTraversal(self, root):
        result = []
        def mid_ord_tra(root):
            if not root:
                return
            mid_ord_tra(root.left)
            resule.append(root.val)
            mid_ord_tra(root.right)
        mid_ord_tra(root)
        return result

tips:dict为空时 not dict是True

第二种方法就是用迭代的方法

自己设置栈来模拟递归

当栈为空或者根节点为空则输出结果

先不断向栈中输入左结点 再把此左节点当作当前根节点

如果当前结点为空则说明左面全部入栈 那么从栈中弹出结点并输入到结果再转向当前结点的右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		stack = []
		while stack or root:
#当栈为空或根节点为空则返回结果
			if root:
#判断是否走到最边边
#节点入栈 节点变更
				stack.append(root)
				root = root.left
			else:
#走到最边边 栈弹出 增加结果 继续走节点右
				root = stack.pop()
				res.append(root.val)
				root = root.right
		return res