首页 > 代码库 > 腾讯笔试题：满二叉排序树，任给3个子节点，找他们最大的公共父节点

腾讯笔试题：满二叉排序树，任给3个子节点，找他们最大的公共父节点

2024-09-12 18:09:10   217人阅读

腾讯笔试题出现了和这个类似的题目，没做出来，现在来好好解决这个问题吧，先从基本的开始。

先吐槽一下：感觉算法设计什么的，真的超级难，也许是我头脑太笨，转不过弯来吧，呵呵。

题目是这样的：一棵满二叉排序树，有K层，节点的值依次为 1~2k-1。现在告诉你树的高度是4层，给定你3个节点，比如9，11， 13，那么最大的公共父节点是12.

现在想起来这题我已经想出来一半了呀，但是大概人在紧张的时候大脑会思维短路，跳不出原有的思维陷阱。想法是这样的：

1. 首先是从根节点开始，如果给的三个叶节点的值其中一个小于根节点另一个大于根节点的话，那不用说了，最大的公共父节点肯定就是根节点了.

2. 不是1的情况的话，那么这3个叶节点要么全在根节点的左部要么全在根节点的右部

3. 向下一层的根节点遍历，直至出现1的情况，此时的节点便是最大的公共父节点了

 

贴上代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        //树的高度
        int k=in.nextInt();
        //最开始根节点的值
        int root=(int)Math.pow(2,k)/2;
        //最开始的最左叶子节点和最右叶子节点
        int leftNode=1;
        int rightNode=(int)Math.pow(2,k)-1;
        //输入3个叶子节点的值
        int node1=in.nextInt();
        int node2=in.nextInt();
        int node3=in.nextInt();
        for(int i=1;i<=k;i++){
            //3个叶子节点全在根节点的左部,更新最右节点和根节点
            if(node1<root&&node2<root&&node3<root){
                rightNode=root-1;
                root=(leftNode+rightNode)/2;
            }
            //3个叶子节点全在根节点的右部,更新最左节点和根节点
            else if(node1>root&&node2>root&&node3>root){
                leftNode=root+1;
                root=(leftNode+rightNode)/2;
            }
            //一大一小的情形下根节点即为最大公共父节点
            else{
                System.out.println(root);
                break;
            }
        }
    }
}

 测试：

技术分享

腾讯笔试题：满二叉排序树，任给3个子节点，找他们最大的公共父节点


联系
我们