[LeetCode]Closest Leaf in a Binary Tree

这道题比较方便的做法是转化成图，然后直接BFS即可。缺点是耗的空间稍微多一点，这里我们仍然有递归的做法，就是稍微麻烦一点。具体来说，递归的时候我们有几种情况:

1. 以当前node为根的子树不包含target节点
2. 以当前node为根的子树包含target节点
3. 当前节点就为target节点

对于上面几种情况，我们需要知道的信息如下:

1. 对于情况1，我们希望知道子树中距离最近的叶节点
2. 对于情况2，在不包含target的那一边，我们希望知道子树中距离最近的叶节点；在包含target的那边，我们希望知道和target的距离
3. 对于情况3，如果其为叶节点，那么答案为0。否则，我们希望知道子树中距离最近的叶节点

另外题目要求我们return对于叶节点的val，所以每次递归的时候我们需要return的值有：

1. 最近的叶节点距离
2. 如果有target，target的距离
3. 对应的叶节点的val

我们用正负值来区分1和2当中的值即可。时间复杂度O(N)，代码如下:

	class Solution {
	public:
	int findClosestLeaf(TreeNode* root, int k) {
	int minD = INT_MAX, res = -1;
	find(root, minD, res, k);
	return res;
	}
	private:
	pair<int, TreeNode*> find(TreeNode* root, int& minD, int& res, int key)
	{
	if (!root)return{ 1005, nullptr };
	if (!root->left && !root->right)
	{
	if (root->val == key)
	{
	minD = 0;
	res = key;
	return { -1, root };
	}
	else
	return { 1, root };
	}
	auto left = find(root->left, minD, res, key);
	auto right = find(root->right, minD, res, key);
	if (root->val == key)
	{
	int currDist = min(left.first, right.first);
	if (currDist < minD)
	{
	minD = currDist;
	res = left.first < right.first ? left.second->val : right.second->val;
	return{ -1, root };
	}
	}
	else
	{
	if (left.first > 0 && right.first > 0)return{ min(left.first, right.first) + 1, left.first < right.first ? left.second: right.second };
	else
	{
	int currDist = abs(left.first) + abs(right.first);
	if (currDist < minD)
	{
	minD = currDist;
	res = left.first > 0 ? left.second->val : right.second->val;
	}
	return{ left.first < 0 ? left.first - 1 : right.first - 1, left.first < 0 ? left.second : right.second };
	}
	}
	}
	};

view raw Closest Leaf in a Binary Tree.cpp hosted with ❤ by GitHub