开发建设网站需要什么人才,影视自助建站系统源码,wordpress特点,优秀网站制作实例展示系列文章#xff1a;
相关题目#xff1a; 94. 二叉树的中序遍历 中序遍历结果为#xff1a;4 2 5 1 6 3 7
总体上分为两种框架#xff0c;递归框架和非递归框架#xff0c;递归框架又分为两种思路#xff1a;分解思路和遍历思路。
递归 1、分解思路 【分解为子问题】…系列文章
相关题目 94. 二叉树的中序遍历 中序遍历结果为4 2 5 1 6 3 7
总体上分为两种框架递归框架和非递归框架递归框架又分为两种思路分解思路和遍历思路。
递归 1、分解思路 【分解为子问题】 2、遍历思路 【更新外部变量】非递归 3、借助栈
下面代码对三种方法逐一实现。 class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass InorderTraversal:94. 二叉树的中序遍历https://leetcode.cn/problems/binary-tree-inorder-traversal/def solution1(self, root):中序遍历:type root: TreeNode:rtype: List[int]if not root:return []return self.solution1(root.left) [root.val] self.solution1(root.right)def solution1_1(self, root):分解思路同上:param root::return:res []if not root:return []res.extend(self.solution1_1(root.left))res.append(root.val)res.extend(self.solution1_1(root.right))return resdef solution2(self, root):遍历思路一般需要借助递归函数递归函数没有返回值靠更新外部变量得到结果:param root::return:self.res []self.traverse(root)return self.resdef traverse(self, node):if not node:returnself.traverse(node.left)self.res.append(node.val)self.traverse(node.right)def solution3(self, root):非递归思路借助栈 实现:param root::return:res []if not root:return reselse:stk []while stk or root:if root:stk.append(root)root root.leftelse:root stk.pop()res.append(root.val)root root.rightreturn res
