Algorithm

华为/腾讯编程题/剑指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;
    }
}