week03_homework

xkluan · xkluan · commit 96ab7eead63a · 2020-06-28T23:59:25.000+08:00
diff --git a/Week03/105-从前序与中序遍历序列构造二叉树.py b/Week03/105-从前序与中序遍历序列构造二叉树.py
@@ -0,0 +1,38 @@
+# 根据一棵树的前序遍历与中序遍历构造二叉树。
+#
+#  注意:
+# 你可以假设树中没有重复的元素。
+#
+#  例如，给出
+#
+#  前序遍历 preorder = [3,9,20,15,7]
+# 中序遍历 inorder = [9,3,15,20,7]
+#
+#  返回如下的二叉树：
+#
+#      3
+#    / \
+#   9  20
+#     /  \
+#    15   7
+#  Related Topics 树 深度优先搜索 数组
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
+        if not (preorder and inorder):
+            return None
+        root = TreeNode(preorder[0])
+        mid_idx = inorder.index(preorder[0])
+        root.left = self.buildTree(preorder[1:mid_idx+1], inorder[:mid_idx])
+        root.right = self.buildTree(preorder[mid_idx+1:], inorder[mid_idx+1:])
+        return root
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week03/236-二叉树的最近公共祖先.py b/Week03/236-二叉树的最近公共祖先.py
@@ -0,0 +1,53 @@
+# 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
+#
+#  百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
+# 一个节点也可以是它自己的祖先）。”
+#
+#  例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
+#
+#
+#
+#
+#
+#  示例 1:
+#
+#  输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
+# 输出: 3
+# 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
+#
+#
+#  示例 2:
+#
+#  输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
+# 输出: 5
+# 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
+#
+#
+#
+#
+#  说明:
+#
+#
+#  所有节点的值都是唯一的。
+#  p、q 为不同节点且均存在于给定的二叉树中。
+#
+#  Related Topics 树
+
+
+# leetcode submit region begin(Prohibit modification and deletion)
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
+        if not root or root == p or root == q: return root
+        left = self.lowestCommonAncestor(root.left, p, q)
+        right = self.lowestCommonAncestor(root.right, p, q)
+        if not left: return right
+        if not right: return left
+        return root
+# leetcode submit region end(Prohibit modification and deletion)
diff --git a/Week03/NOTE.md b/Week03/NOTE.md
@@ -1 +1,11 @@
-学习笔记
+学习笔记
+# 回溯
+回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将
+取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问
+题的答案。
+回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种
+情况:
+
+• 找到一个可能存在的正确的答案;
+
+• 在尝试了所有可能的分步方法后宣告该问题没有答案。 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。
