Add 235 236

hapiman2 · hapiman2 · commit cf8110086d0e · 2018-11-05T23:23:12.000+08:00
diff --git a/src/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/README.md b/src/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/README.md
@@ -0,0 +1,69 @@
+# [236. Lowest Common Ancestor of a Binary Tree][title]
+
+## Description
+
+Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
+
+According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
+
+Given binary search tree:  `root = [6,2,8,0,4,7,9,null,null,3,5]`
+
+```
+       _______6______
+       /              \
+    ___2__          ___8__
+   /      \        /      \
+   0      _4       7       9
+         /  \
+         3   5
+```
+
+**Example 1:**
+
+Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
+
+Output: 6
+
+Explanation: The LCA of nodes 2 and 8 is 6.
+
+**Example 2:**
+
+Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
+
+Output: 2
+
+Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself
+             according to the LCA definition.
+
+## NOTES
+
+- All of the nodes' values will be unique.
+- `p` and `q` are different and both values will exist in the BST.
+
+**Tags:** Binary Search Tree (BST)
+
+## 题意
+> 在二叉搜索树中查询两个节点最近的祖先元素
+
+### 思路1
+定义节点，直接左右递归, 详见代码。
+
+代码实现可以查考`0236`实现， 但是考虑到`BST`的有序性, 判断逻辑可以更加精简。
+```go
+func Lowest(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
+	if p.val < root.val && q.val < root.val {
+		return Lowest(root.left, p, q)
+	}
+	if p.val > root.val && q.val > root.val {
+		return Lowest(root.right, p, q)
+	}
+	return root
+}
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-letcode][me]
+
+[title]: https://leetcode.com/problems/valid-anagram/description/
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/Solution.go b/src/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/Solution.go
@@ -0,0 +1,17 @@
+package Solution
+
+type TreeNode struct {
+	val   int
+	left  *TreeNode
+	right *TreeNode
+}
+
+func Lowest(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
+	if p.val < root.val && q.val < root.val {
+		return Lowest(root.left, p, q)
+	}
+	if p.val > root.val && q.val > root.val {
+		return Lowest(root.right, p, q)
+	}
+	return root
+}
diff --git a/src/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/Solution_test.go b/src/0235.Lowest-Common-Ancestor-of-a-Binary-Search-Tree/Solution_test.go
@@ -0,0 +1,55 @@
+package Solution
+
+import (
+	"testing"
+)
+
+// 测试样例 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
+func TestSolution(t *testing.T) {
+	tNode := &TreeNode{}
+	tNode.val = 6
+
+	tNode1 := &TreeNode{}
+	tNode1.val = 2
+
+	tNode2 := &TreeNode{}
+	tNode2.val = 8
+
+	tNode3 := &TreeNode{}
+	tNode3.val = 0
+
+	tNode4 := &TreeNode{}
+	tNode4.val = 4
+
+	tNode5 := &TreeNode{}
+	tNode5.val = 7
+
+	tNode6 := &TreeNode{}
+	tNode6.val = 9
+
+	tNode9 := &TreeNode{}
+	tNode9.val = 3
+
+	tNode10 := &TreeNode{}
+	tNode10.val = 5
+
+	// 第一层
+	tNode.left = tNode1
+	tNode.right = tNode2
+
+	// 第二层
+	tNode1.left = tNode3
+	tNode1.right = tNode4
+	tNode2.left = tNode5
+	tNode2.right = tNode6
+
+	// 第三层
+	tNode4.left = tNode9
+	tNode4.right = tNode10
+
+	luckyNode := Lowest(tNode, tNode1, tNode2)
+	t.Logf("luckyNode.value = %d", luckyNode.val)
+	if luckyNode != tNode {
+		t.Fatalf("Unlucky, false.")
+	}
+}
diff --git a/src/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/README.md b/src/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/README.md
@@ -0,0 +1,62 @@
+# [236. Lowest Common Ancestor of a Binary Tree][title]
+
+## Description
+
+Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
+
+According to the definition of [LCA on Wikipedia](https://en.wikipedia.org/wiki/Lowest_common_ancestor): “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
+
+Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]
+
+```
+_______3______
+       /              \
+    ___5__          ___1__
+   /      \        /      \
+   6      _2       0       8
+         /  \
+         7   4
+```
+
+**Example 1:**
+
+Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
+
+Output: 3
+
+Explanation: The LCA of of nodes 5 and 1 is 3.
+
+**Example 2:**
+
+Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
+
+Output: 5
+
+Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
+             according to the LCA definition.
+
+## NOTES
+- All of the nodes' values will be unique.
+- `p` and `q` are different and both values will exist in the binary tree.
+
+**Tags:** Binary Tree
+
+## 题意
+> 查找二叉树某两个节点最近的祖先元素
+
+### 思路1
+定义节点，直接左右递归, 详见代码
+```go
+type TreeNode struct {
+	val   int
+	left  *TreeNode
+	right *TreeNode
+}
+```
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-letcode][me]
+
+[title]: https://leetcode.com/problems/valid-anagram/description/
+[me]: https://github.com/kylesliu/awesome-golang-leetcode
diff --git a/src/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/Solution.go b/src/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/Solution.go
@@ -0,0 +1,22 @@
+package Solution
+
+type TreeNode struct {
+	val   int
+	left  *TreeNode
+	right *TreeNode
+}
+
+func Lowest(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
+	if root == nil || p == root || q == root {
+		return root
+	}
+	left := Lowest(root.left, p, q)
+	right := Lowest(root.right, p, q)
+	if left == nil {
+		return right
+	}
+	if right == nil {
+		return left
+	}
+	return root
+}
diff --git a/src/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/Solution_test.go b/src/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/Solution_test.go
@@ -0,0 +1,54 @@
+package Solution
+
+import (
+	"testing"
+)
+
+// 测试样例 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
+func TestSolution(t *testing.T) {
+	tNode := &TreeNode{}
+	tNode.val = 3
+
+	tNode1 := &TreeNode{}
+	tNode1.val = 5
+
+	tNode2 := &TreeNode{}
+	tNode2.val = 1
+
+	tNode3 := &TreeNode{}
+	tNode3.val = 6
+
+	tNode4 := &TreeNode{}
+	tNode4.val = 2
+
+	tNode5 := &TreeNode{}
+	tNode5.val = 0
+
+	tNode6 := &TreeNode{}
+	tNode6.val = 8
+
+	tNode9 := &TreeNode{}
+	tNode9.val = 7
+
+	tNode10 := &TreeNode{}
+	tNode10.val = 4
+
+	// 第一层
+	tNode.left = tNode1
+	tNode.right = tNode2
+
+	// 第二层
+	tNode1.left = tNode3
+	tNode1.right = tNode4
+	tNode2.left = tNode5
+	tNode2.right = tNode6
+
+	// 第三层
+	tNode4.left = tNode9
+	tNode4.right = tNode10
+
+	luckyNode := Lowest(tNode, tNode1, tNode2)
+	if luckyNode != tNode {
+		t.Fatalf("Unlucky, false.")
+	}
+}
