742. Closest Leaf in a Binary Tree的思路

题目大意是，找到最临近给定节点的叶节点，例如

1/ \2 3/4/5/6

给定2的话，最近的是3，给定4的话，最近的是6。

思路：题目中，树的结构并不利于寻找答案，需要把树的结构转换成图，然后通过广度优先搜索，可以轻易的获取最近的叶节点。

代码：

class Solution {public:int findClosestLeaf(TreeNode* root, int k) {kv=k;for(int i=0;i<1010;i++){f[i]=false;v[i]=false;}helper(root);queue<int> q;q.push(k);int res=0;while(q.size()>0){int tk=q.front();if(f[tk] == true)return tk;q.pop();if( v[tk] == false){v[tk]=true;res++;int ns=n[tk].size();for(int i=0;i<ns;i++){int tki=n[tk][i];if(f[tki] == true)return tki;if(v[tki] == false){q.push(tki);}}}}return -1;}void helper(TreeNode* t){if(t == NULL)return;if(t->left == NULL && t->right == NULL){f[t->val]=true;return;}if(t->left !=NULL){n[t->left->val].push_back(t->val);n[t->val].push_back(t->left->val);helper(t->left);}if(t->right !=NULL){n[t->right->val].push_back(t->val);n[t->val].push_back(t->right->val);helper(t->right);}}private:vector<int> n[1010];bool f[1010];bool v[1010];int kv;};

代码结构，是分两步，第一步通过helper函数，将树转化成无权邻域矩阵，第二步，在主函数里通过广度优先搜索，寻找最短路径。