求树中两个节点的最低公共父节点

水深无声 2022-06-17 01:19 217阅读 0赞

这个题目其实是具有二义性的，因为没有对树的结构进行说明，例如二叉树搜索树，具有指向父节点引用的树，和普通的树，针对三种情况对应的处理方式是不同的，接下来我们结合三种情况来具体分析一下：

# 二叉搜索树 #

根据二叉搜索树的性质，根节点大于其左节点，小于其右节点，因此我们可以用这个条件来判断，找到最低的大于leftnode且小于rightnode的那个节点即是目标：

public class BinaryTreeNode {
        public int value;
        public BinaryTreeNode leftNode;
        public BinaryTreeNode rightNode;
    
        public BinaryTreeNode(int value) {
            //搜索二叉树是否平衡与元素的插入顺序是有关的
            this.value = value;
            leftNode = null;
            rightNode = null;
        }
    
        public static BinaryTreeNode getLowestCommonAncestor(BinaryTreeNode rootParent, BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2) {
            if (root == null || node1 == null || node2 == null) {
                return null;
            }
            if ((root.value - node1.value) * (root.value - node2.value) < 0) {
                return root;
            } else if ((root.value - node1.value) * (root.value - node2.value) > 0) {
                BinaryTreeNode newRoot = ((root.value > node1.value) && (root.value > node2.value)) ? root.leftNode : root.rightNode;
                return getLowestCommonAncestor(root, newRoot, node1, node2);
            } else {
                return rootParent;
            }
        }
    
    
        public static void main(String[] args) {
            BinaryTreeNode A = new BinaryTreeNode(4);
            BinaryTreeNode B = new BinaryTreeNode(2);
            BinaryTreeNode C = new BinaryTreeNode(6);
            BinaryTreeNode D = new BinaryTreeNode(1);
            BinaryTreeNode E = new BinaryTreeNode(3);
            BinaryTreeNode F = new BinaryTreeNode(5);
            BinaryTreeNode G = new BinaryTreeNode(7);
            A.leftNode = B;
            A.rightNode = C;
            B.leftNode = D;
            B.rightNode = E;
            C.leftNode = F;
            C.rightNode = G;
            BinaryTreeNode res1 = getLowestCommonAncestor(null, A, E, F);
            BinaryTreeNode res2 = getLowestCommonAncestor(null, A, D, E);
            BinaryTreeNode res3 = getLowestCommonAncestor(null, A, B, D);
            System.out.println("The lowest common ancestor of 3 and 5 is " + res1.value);
            System.out.println("The lowest common ancestor of 1 and 3 is " + res2.value);
            System.out.println("The lowest common ancestor of 1 and 2 is " + res3.value);
        }
    }

使用的例子如图：

![这里写图片描述][SouthEast]

（注：后续两个例子的树的构造同理，故不再赘述）

# 具有指向父节点引用的树 #

可以将问题看做两个链表求最先公共结点的问题，因此需要先求出包含两个目标节点所构成的“链表”的长度：

public class NewBinaryTreeNode {
        public int value;
        public NewBinaryTreeNode parentNode;
        public NewBinaryTreeNode leftNode;
        public NewBinaryTreeNode rightNode;
    
        public NewBinaryTreeNode(int value) {
            this.value = value;
            parentNode = null;
            leftNode = null;
            rightNode = null;
        }
    
    
        public static NewBinaryTreeNode getLowestCommonAncestor1(NewBinaryTreeNode root, NewBinaryTreeNode node1, NewBinaryTreeNode node2) {
            if (root == null || node1 == null || node2 == null) {
                return null;
            }
            int depth1 = findTheDepthOfTheNode(root, node1, node2);
            if (depth1 == -1) {
                return node2.parentNode;
            }
            int depth2 = findTheDepthOfTheNode(root, node2, node1);
            if (depth2 == -1) {
                return node1.parentNode;
            }
            //p指向较深的节点q指向较浅的节点
            NewBinaryTreeNode p = depth1 > depth2 ? node1 : node2;
            NewBinaryTreeNode q = depth1 > depth2 ? node2 : node1;
            int depth = Math.abs(depth1 - depth2);
            while (depth > 0) {
                p = p.parentNode;
                depth--;
            }
            while (p != q) {
                p = p.parentNode;
                q = q.parentNode;
            }
            return p;
        }
    
        //求node1的深度，如果node1和node2在一条路径上，则返回-1，否则返回node1的深度
        public static int findTheDepthOfTheNode(NewBinaryTreeNode root, NewBinaryTreeNode node1, NewBinaryTreeNode node2) {
            int depth = 0;
            while (node1.parentNode != null) {
                node1 = node1.parentNode;
                depth++;
                if (node1 == node2) {
                    return -1;
                }
            }
            return depth;
        }
    
    }

# 普通的树 #

同样可以看作是链表的问题，不过由于没有指向父节点的引用，因此不能由下往上进行，但是同样可以看成两条包含目标节点的问题，即求两条链表的最后公共结点问题，使用辅助栈存储包含目标节点的路径，即可完成：

//转换成为求两个链表的最后公共结点问题
    public class CommonBinaryNode {
        
        //BinaryTreeNode是同包中的public类，可以直接使用其数据结构
        public static BinaryTreeNode getLowestCommonAncestor2(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2){
            if(root == null || node1 == null || node2 == null){
                return null;
            }
            Stack<BinaryTreeNode> path1 = new Stack<BinaryTreeNode>();
            boolean flag1 = getThePathOfTheNode(root, node1,path1);
            if(!flag1){
       //树上没有node1节点
                return null;
            }
            Stack<BinaryTreeNode> path2 = new Stack<BinaryTreeNode>();
            boolean flag2 = getThePathOfTheNode(root, node2,path2);
            if(!flag2){
       //树上没有node2节点
                return null;
            }
            if(path1.size() > path2.size()){ //让两个路径等长
                while(path1.size() !=  path2.size()){
                    path1.pop();
                }
            }else{
                while(path1.size() !=  path2.size()){
                    path2.pop();
                }
            }
            if(path1.equals(path2)){
       //当两个节点在一条路径上时
                path1.pop();
                return path1.pop();
            }else{
                BinaryTreeNode p = path1.pop();
                BinaryTreeNode q = path2.pop();
                while(q != p){
                    p = path1.pop();
                    q = path2.pop();
                }
                return p;
            }
        }
    
        //获得根节点到node节点的路径
        public static boolean getThePathOfTheNode(BinaryTreeNode root,BinaryTreeNode node,Stack<BinaryTreeNode> path){
            path.push(root);
            if(root == node){
                return true;
            }
            boolean found = false;
            //前序遍历整棵树
            if(root.leftNode != null){
                found = getThePathOfTheNode(root.leftNode, node, path);
            }
            if(!found && root.rightNode != null){
                found = getThePathOfTheNode(root.rightNode, node, path);
            }
            if(!found){
                path.pop();
            }
            return found;
        }
    }

[SouthEast]: /images/20220617/551d432aaf8f4f40a1a3091680b5494b.png