Skip to content

Commit a243f7f

Browse files
pphdsnypphdsny
committed
feat(TreeNode): 236-lowestCommonAncestor
1 parent 2b49e23 commit a243f7f

3 files changed

Lines changed: 167 additions & 31 deletions

File tree

‎src/pp/arithmetic/Util.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import pp.arithmetic.easy._206_ReverseList;
44
import pp.arithmetic.model.ListNode;
5+
import pp.arithmetic.model.TreeNode;
56

67
import java.util.List;
78
import java.util.Random;
@@ -78,6 +79,29 @@ public static int[] generateArrayBySize(int maxSize) {
7879
return nums;
7980
}
8081

82+
public static TreeNode generateTreeNode() {
83+
TreeNode root = new TreeNode(5);
84+
TreeNode node1 = new TreeNode(4);
85+
TreeNode node2 = new TreeNode(8);
86+
TreeNode node3 = new TreeNode(11);
87+
TreeNode node4 = new TreeNode(13);
88+
TreeNode node5 = new TreeNode(4);
89+
TreeNode node6 = new TreeNode(7);
90+
TreeNode node7 = new TreeNode(2);
91+
TreeNode node8 = new TreeNode(5);
92+
TreeNode node9 = new TreeNode(1);
93+
root.left = node1;
94+
root.right = node2;
95+
node1.left = node3;
96+
node2.left = node4;
97+
node2.right = node5;
98+
node3.left = node6;
99+
node3.right = node7;
100+
node5.left = node8;
101+
node5.right = node9;
102+
return root;
103+
}
104+
81105
public static void printArray(int[] nums) {
82106
for (int i = 0; i < nums.length; i++) {
83107
System.out.print(nums[i] + " ");
@@ -102,4 +126,20 @@ public static void printStringList(List<String> nums) {
102126
public static void printDivideLine() {
103127
System.out.println("-------我是分割线-------");
104128
}
129+
130+
public static void printTree(TreeNode treeNode) {
131+
printTree(treeNode, 0);
132+
}
133+
134+
private static void printTree(TreeNode treeNode, int floor) {
135+
if (treeNode == null) {
136+
return;
137+
}
138+
for (int i = 0; i < floor; i++) {
139+
System.out.print("----");
140+
}
141+
System.out.println("[" + treeNode.val + "]");
142+
printTree(treeNode.left, floor + 1);
143+
printTree(treeNode.right, floor + 1);
144+
}
105145
}

‎src/pp/arithmetic/medium/_113_pathSum.java‎

Lines changed: 8 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -16,13 +16,13 @@
1616
* 示例:
1717
* 给定如下二叉树，以及目标和 sum = 22，
1818
* <p>
19-
* 5
20-
* / \
21-
* 4 8
22-
* / / \
23-
* 11 13 4
24-
* / \ / \
25-
* 7 2 5 1
19+
* 5
20+
* / \
21+
* 4 8
22+
* / / \
23+
* 11 13 4
24+
* / \ / \
25+
* 7 2 5 1
2626
* 返回:
2727
* <p>
2828
* [
@@ -34,36 +34,13 @@
3434
*/
3535
public class _113_pathSum {
3636
public static void main(String[] args) {
37-
TreeNode treeNode = generateTree();
37+
TreeNode treeNode = Util.generateTreeNode();
3838
List<List<Integer>> lists = pathSum(treeNode, 22);
3939
for (int i = 0; i < lists.size(); i++) {
4040
Util.printList(lists.get(i));
4141
}
4242
}
4343

44-
private static TreeNode generateTree() {
45-
TreeNode root = new TreeNode(5);
46-
TreeNode node1 = new TreeNode(4);
47-
TreeNode node2 = new TreeNode(8);
48-
TreeNode node3 = new TreeNode(11);
49-
TreeNode node4 = new TreeNode(13);
50-
TreeNode node5 = new TreeNode(4);
51-
TreeNode node6 = new TreeNode(7);
52-
TreeNode node7 = new TreeNode(2);
53-
TreeNode node8 = new TreeNode(5);
54-
TreeNode node9 = new TreeNode(1);
55-
root.left = node1;
56-
root.right = node2;
57-
node1.left = node3;
58-
node2.left = node4;
59-
node2.right = node5;
60-
node3.left = node6;
61-
node3.right = node7;
62-
node5.left = node8;
63-
node5.right = node9;
64-
return root;
65-
}
66-
6744
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
6845
List<List<Integer>> result = new ArrayList<>();
6946
List<Integer> path = new ArrayList<>();

‎src/pp/arithmetic/medium/_236_lowestCommonAncestor.java‎

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
package pp.arithmetic.medium;
2+
3+
import pp.arithmetic.Util;
4+
import pp.arithmetic.model.TreeNode;
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
9+
/**
10+
* Created by wangpeng on 2018/9/14.
11+
* 236.二叉树的最近公共祖先
12+
* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
13+
* <p>
14+
* 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
15+
* <p>
16+
* 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
17+
* <p>
18+
* _______3______
19+
* / \
20+
* ___5__ ___1__
21+
* / \ / \
22+
* 6 _2_ 0 8
23+
* / \
24+
* 7 4
25+
* 示例 1:
26+
* <p>
27+
* 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
28+
* 输出: 3
29+
* 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
30+
* 示例 2:
31+
* <p>
32+
* 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
33+
* 输出: 5
34+
* 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
35+
* 说明:
36+
* <p>
37+
* 所有节点的值都是唯一的。
38+
* p、q 为不同节点且均存在于给定的二叉树中。
39+
*
40+
* @see <a href="https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/description/">lowest-common-ancestor-of-a-binary-tree</a>
41+
*/
42+
public class _236_lowestCommonAncestor {
43+
public static void main(String[] args) {
44+
TreeNode treeNode = Util.generateTreeNode();
45+
Util.printTree(treeNode);
46+
TreeNode treeNode1 = lowestCommonAncestor(treeNode, treeNode.left.left, treeNode.left);
47+
System.out.println(treeNode1.val);
48+
//更优
49+
TreeNode treeNode2 = lowestCommonAncestor2(treeNode, treeNode.left.left, treeNode.left);
50+
System.out.println(treeNode2.val);
51+
}
52+
53+
private static boolean isFinish = false;
54+
55+
/**
56+
* 时间复杂度：O(n),不过这3*O(n)比方案2要复杂
57+
*
58+
* @param root
59+
* @param p
60+
* @param q
61+
* @return
62+
*/
63+
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
64+
List<TreeNode> qList = new ArrayList<>();
65+
List<TreeNode> pList = new ArrayList<>();
66+
isFinish = false;
67+
dfs(root, p, pList);
68+
isFinish = false;
69+
dfs(root, q, qList);
70+
TreeNode result = null;
71+
for (int i = 0; i < qList.size() && i < pList.size(); i++) {
72+
if (pList.get(i) != qList.get(i)) {
73+
break;
74+
}
75+
result = pList.get(i);
76+
}
77+
return result;
78+
}
79+
80+
private static void dfs(TreeNode root,
81+
TreeNode target,
82+
List<TreeNode> path) {
83+
if (root == null || isFinish) {
84+
return;
85+
}
86+
if (root == target) {
87+
isFinish = true;
88+
}
89+
path.add(root);
90+
dfs(root.left, target, path);
91+
dfs(root.right, target, path);
92+
if (!isFinish) {
93+
path.remove(path.size() - 1);
94+
}
95+
}
96+
97+
/**
98+
* 采用的是后序遍历。
99+
* 如果需要找的两个节点分别在我的左，右，那么我就是最近的父节点
100+
* 如果只在我的left，那么left就是最近父节点，反之则是在right
101+
* 时间复杂度：O(n)
102+
*
103+
* @param root
104+
* @param p
105+
* @param q
106+
* @return
107+
*/
108+
public static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
109+
if (root == null || root == p || root == q) {
110+
return root;
111+
}
112+
TreeNode leftNode = lowestCommonAncestor2(root.left, p, q);
113+
TreeNode rightNode = lowestCommonAncestor2(root.right, p, q);
114+
if (leftNode != null && rightNode != null) {
115+
return root;
116+
}
117+
return leftNode == null ? rightNode : leftNode;
118+
}
119+
}

0 commit comments

Comments
 (0)