FilesExpand file tree

 master

/

LeetCode236.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

46 lines (44 loc) · 1.55 KB

 master

/

LeetCode236.java

Top

File metadata and controls

• Code
• Blame

46 lines (44 loc) · 1.55 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

package problems;

public class LeetCode236 {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if(root == null || root == p || root == q) {

return root;

}

// 根节点不是 p 和 q 中的任意一个，那么就继续分别往左子树和右子树找 p 和 q

TreeNode left = lowestCommonAncestor(root.left, p, q);

TreeNode right = lowestCommonAncestor(root.right, p, q);

// p 和 q 都没有找到，那就没有

if (left == null && right == null) {

return null;

}

// 左子树没有 p 也没有 q，就返回右子树的结果

if (left == null) {

return right;

}

// 右子树没有 p 也没有 q，就返回左子树的结果

if(right == null) {

return left;

}

// 左右子树都找到 p 和 q 了，那就说明 p 和 q 分别在左右两个子树上，所有此时的最近公共祖先就是 root

return root;

}

}

class LeetCode236_1 {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if(root == null || root == p || root == q) {

return root;

}

TreeNode left = lowestCommonAncestor(root.left, p, q);

TreeNode right = lowestCommonAncestor(root.right, p, q);

if(left == null && right == null) {

return null;

}

if(left == null) {

return right;

}

if(right == null) {

return left;

}

return root;

}

}