0%

华为/腾讯编程题/剑指Offer50---两个结点的最低公共父节点

树中两个节点的最低公共祖先

思路一:二叉搜索树

树是二叉树,而且是二叉搜索树的情况,因为二叉搜索树都是排序过的,位于左子树的节点都比父节点小,而位于右子树上面的节点都比父节点大。

  • 如果当前节点的值比两个结点 的值都大,那么最低的共同的父节点一定是在当前节点的左子树中,于是下一步遍历当前节点的左子节点。
  • 如果当前节点的值比两个结点的值都小,那么最低的共同的父节点一定是在当前节点的右子树中,于是下一步遍历当前节点的右子节点。
  • 这样从上到下,找到的第一个在两个输入结点的值之间的节点,就是最低的公共祖先。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode {
int data;
TreeNode left;
TreeNode right;
}

public class Solution {
public static TreeNode getLastCommonParent(TreeNode root, TreeNode a, TreeNode b) {
if(root == null || a == null || b == null)
return null;
while(root != null) {
if (root.data > a.data && root.data > b.data) {
root = root.left;
} else if (root.data < a.data && root.data < b.data) {
root = root.right;
} else
return root;
}
return null;
}
}

思路二:带父节点指针的树

直接从两个节点向上遍历,直到遍历到公共节点为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode parent;
}

public class Solution {
public static TreeNode getLastCommonParent(TreeNode a, TreeNode b) {
if(a == null || b == null)
return null;
TreeNode aParent = a;
TreeNode bParent = b;
while(aParent != null && bParent != null) {
if(aParent.data != bParent.data) {
aParent = aParent.parent;
bParent = bParent.parent;
} else {
return aParent;
}
}
return null;
}
}

思路三:深度优先搜索

从叶子节点向上,标记子树中出现目标节点的情况。如果子树中有目标节点则将子树标记为目标节点,如果没有则标记为空。当左右子树都有标记时,则找到了最低公共祖先了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode {
int data;
TreeNode left;
TreeNode right;
}

public class Solution {
public static TreeNode getLastCommonParent(TreeNode root, TreeNode a, TreeNode b) {
if(root == null || root == a || root == b)
return root;
TreeNode left = getLastCommonParent(root.left, a, b);
TreeNode right = getLastCommonParent(root.right, a, b);

//都不为空,说明左右子树都有目标结点,则公共祖先就是本身
if(left != null && right != null)
return root;

//如果发现了目标节点,则继续向上标记为该目标节点
return left == null ? right : left;
}
}

以上解法需要对同一个结点重复遍历很多次,效率较低。

思路四:使用辅助内存

用两个栈记录从根节点到两节点的路径,转化为求链表的最后一个公共节点
当找到给定节点的时候才将路径依次压入stack中,也就是说,两个stack的栈顶都是存放着root节点。因此,此时就应该找两条路径分离开之前的最后一个节点,此节点就是所求的最低公共祖先。

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
class TreeNode {
int data;
TreeNode left;
TreeNode right;
}

public class Solution {
public static TreeNode getLastCommonParent(TreeNode root, TreeNode a, TreeNode b){
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
getPath(root, a, stack1);
getPath(root, b, stack2);
return getLastCommonTreeNode(stack1, stack2);
}
public static TreeNode getLastCommonTreeNode(Stack<TreeNode> stack1, Stack<TreeNode> stack2) {
TreeNode target = null;
while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek()) {
target = stack1.peek();
stack1.pop();
stack2.pop();
}
return target;
}

//获取从根节点到target节点的路径
public static boolean getPath(TreeNode root, TreeNode target, Stack<TreeNode> stack) {
if(root == null)
return false;
if(root == target) {
stack.push(root);
return true;
} else {
if(getPath(root.left, target, stack) || getPath(root.right, target, stack) {
stack.push(root);
return true;
}
}
return false;
}
}
-------------本文结束感谢您的阅读-------------