首页 > 试题广场 >

给出二叉树接口，找出值为val的最浅节点所在层数。

[问答题]

给出二叉树接口为

class node
{
    node *get_left();
    node *get_right();
    int get_data();
}

找出值为val的最浅节点所在层数。

int find(node *root, int val).

查看答案及解析

推荐

Forever@贝

int find(node * root, int val) {
    int ret = 1;

    if (root->get_data() == val) {
        return ret;
    } else {
        int  ret1 = 1 + find(root->get_left(), val);
        int  ret2 = 1 + find(root->get_right(), val);
        if (ret1 > ret2)
            ret = ret2;
        else
            ret = ret1;

        return ret;
    }
}

编辑于 2015-02-03 20:20:04 回复(0)

hxr-osf

int find(node * root, int val) {
    int ret = 1;

    if (root->get_data() == val) {
        return ret;
    } else {
        ret1 = find(root->get_left(), val);
        ret2 = find(root->get_right(), val);
        if (ret1 > ret2)
            ret = ret2;
        else
            ret = ret1;

        return ret;
    }
}

编辑于 2015-02-03 20:16:40 回复(1)

Yano_nankai

层序遍历

发表于 2015-08-09 19:05:12 回复(1)

叫我大头

我看大家都定义了一个局部变量保存层次

我想问递归时里面局部变量为啥会变。在PHP中必须变量定义为 static才会跟随递归变

编辑于 2017-12-27 14:44:56 回复(0)

牛客-hiro

与二叉树的深度是一样的原理。

发表于 2017-03-18 10:24:52 回复(0)

KissGoodbye

/**
	 * 找出值为val的最浅节点所在层数。
	 * 
	 * @param tree
	 * @param val
	 * @return
	 */
	public static int findVal(Tree tree, int val) {
		if (tree == null || tree.root == null) {
			return -1;
		}
		Queue<Node> que = new LinkedList<>();
		que.add(tree.root);
		int levels = 0;
		while (!que.isEmpty()) {
			int length = que.size();
			while (length > 0) {
				Node node = que.poll();
				if (node.data == val) {
					return ++levels;
				}
				if (node.leftChild != null)
					que.add(node.leftChild);
				if (node.rightChild != null)
					que.add(node.rightChild);
				length--;
			}
			levels++;
		}
		return -1;
	}

发表于 2017-03-16 12:25:00 回复(0)

大卫不加班

程序遍历，没那么多花里胡哨的

发表于 2019-03-30 22:28:56 回复(0)

蘅景

//C#版
int find(node root,int val)
	{
		if(root == null)
		{
			return 0;
		}
		else{
			if(root.get_data() == val)
			{
				return 1;
			}
			else
			{
				int left = find(root.get_left(),val);
				int right = find(root.get_right(),val);
				if(left == 0 && right == 0)
				{
					return 0;
				}
				else
				{
					return left+right+1;
				}
			}
		}
	}

发表于 2016-03-03 10:11:30 回复(0)

guanxianseng

//层序遍历


int find(TreeNode root, int val){
		int deep = 0;
		if(root == null)
			return -1;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		boolean found = false;
		while(!queue.isEmpty()){
			Queue<TreeNode> cur = new LinkedList<TreeNode>();
			while(!queue.isEmpty()){
				TreeNode temp = queue.poll();
				if(temp.val == val){
					found = true;
					break;
				}
				if(temp.left != null)
					cur.add(temp.left);
				if(temp.right != null)
					cur.add(temp.right);
			}//while
			deep++;
			while(!cur.isEmpty()){
				queue.add(cur.poll());
			}//while
		}//while
		if(!found)
			return -1;
		return deep;
	}

编辑于 2015-08-14 15:01:44 回复(0)

柏拉图个啥

根节点位于第一层，向下依次第二、三。。。，若所查找的值不存在，返回-1

int find(node *root, int val)
{
    if(NULL==root)
        return -1;
    std::queue<node*> Queue1,Queue2;
    std::queue<node*> *pLevel1 = &Queue1,*pLevel2 = &Queue2;
    int level = 1;
    Queue1.push(root);
    while((*pLevel1).size()!=0)
    {
        while(0!=pLevel1->size())
        {
            if(val==pLevel1->front()->get_data())
            {
                return level;
            }
            else
            {
                if(NULL!=pLevel1->front()->get_left())
                    pLevel2->push(pLevel1->front()->get_left());
                if(NULL!=pLevel1->front()->get_right())
                    pLevel2->push(pLevel2->front()->get_right());
                pLevel1->pop();
            }
        }
        ++level;
        std::queue<node*> *temp = pLevel1;
        pLevel1 = pLevel2;
        pLevel2 = temp;        
    }
    return -1;
}

发表于 2015-03-30 17:33:40 回复(0)

sss534534

int find(node *root, int val) {
    if (root == NULL) {
         return -1;
    }

    if (root->get_data() == val) {
        return 1;
    }
    
     int left = find(root->get_left(), val);
     int right = find(root->get_right(), val);
     if (left != -1 && right != -1)
           return min(left, right);
       else if (left != -1) {
          return left;
       } else if (right != -1) {
            return right;
       } else {
            return -1;
       }
}

编辑于 2015-02-03 20:12:52 回复(0)

Wills

{

int left = 0;

int right = 0;

if(root == NULL)

{

return 1;

}

else if(root.get_data == val)

{

return 0;

}

left = find(root.get_left, val);

right = find(root.get_right, val);

if(left <= right)

{

return left + 1;

}

else

{

return right + 1;

}

发表于 2014-12-03 22:30:31 回复(0)

撒

asczc

发表于 2014-11-18 20:11:59 回复(0)

奇闻看看

递归？

发表于 2014-11-17 23:10:52 回复(0)

提交观点

问题信息

树人人网

来自：人人网2015研发笔试卷A

上传者：偶尔做天使

难度：

14条回答 68收藏 18627浏览

给出二叉树接口，找出值为val的最浅节点所在层数。

问题信息

热门推荐

相关试题