如何做一间公司的网站,企业网络推广情况介绍,了解目前网站建设情况,网站建设小说毕业设计文章目录1. 题目2. 解题1. 题目
给定一个 每个结点的值互不相同 的二叉树#xff0c;和一个目标值 k#xff0c;找出树中与目标值 k 最近的叶结点。
这里#xff0c;与叶结点 最近 表示在二叉树中到达该叶节点需要行进的边数与到达其它叶结点相比最少。 而且#xff0c;当…
文章目录1. 题目2. 解题1. 题目
给定一个 每个结点的值互不相同 的二叉树和一个目标值 k找出树中与目标值 k 最近的叶结点。
这里与叶结点 最近 表示在二叉树中到达该叶节点需要行进的边数与到达其它叶结点相比最少。 而且当一个结点没有孩子结点时称其为叶结点。
在下面的例子中输入的树以逐行的平铺形式表示。 实际上的有根树 root 将以TreeNode对象的形式给出。
示例 1
输入
root [1, 3, 2], k 1
二叉树图示1/ \3 2输出 2 (或 3)
解释 2 和 3 都是距离目标 1 最近的叶节点。示例 2
输入
root [1], k 1
输出1
解释 最近的叶节点是根结点自身。示例 3
输入
root [1,2,3,4,null,null,null,5,null,6], k 2
二叉树图示1/ \2 3/4/5/6输出3
解释 值为 3而不是值为 6的叶节点是距离结点 2 的最近结点。注
root 表示的二叉树最少有 1 个结点且最多有 1000 个结点。
每个结点都有一个唯一的 node.val 范围为 [1, 1000]。
给定的二叉树中有某个结点使得 node.val k。来源力扣LeetCode 链接https://leetcode-cn.com/problems/closest-leaf-in-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dfs 建立父节点信息找到 k 节点加入队列BFS向子节点和父节点进行BFS搜索第一个找到的叶子节点为答案
class Solution {unordered_mapTreeNode*,TreeNode* father;queueTreeNode* q;unordered_setTreeNode* visited;
public:int findClosestLeaf(TreeNode* root, int k) {father[root] NULL;dfs(root, k);int size;TreeNode* cur;while(!q.empty()){size q.size();while(size--){cur q.front();q.pop();if(!cur-left !cur-right)return cur-val;if(cur-left !visited.count(cur-left)){q.push(cur-left);visited.insert(cur-left);}if(cur-right !visited.count(cur-right)){q.push(cur-right);visited.insert(cur-right);}if(father[cur] !visited.count(father[cur])){q.push(father[cur]);visited.insert(father[cur]);}}}return -1;}void dfs(TreeNode* root, int k) {if(!root) return;if(root-val k){q.push(root);visited.insert(root);}if(root-left)father[root-left] root;if(root-right)father[root-right] root;dfs(root-left,k);dfs(root-right,k);}
};28 ms 22.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
