[LeetCode]Smallest Subtree with all the Deepest Nodes

递归的题目，题目虽然说是深度但是我们用高度是一样的。递归的时候我们每次返回两个值，以当前node为根的最大高度h和当前子树的SSDN(Smallest Subtree with all the Deepest Nodes)。那么在每个节点我们要做的决策如下：

• 如果左子树的h大于右子树的h，我们要继续return左子树的h + 1和SSDN
• 如果右子树的h大于右子树的h，我们继续return右子树的h + 1和SSDN
• 如果左右子树h相等，我们return h + 1和当前节点

时间复杂度O(N)，代码如下:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* subtreeWithAllDeepest(TreeNode* root) {
	return dfs(root).second;
	}
	private:
	pair<int, TreeNode*> dfs(TreeNode* curr)
	{
	if(!curr)return {0, nullptr};
	auto left = dfs(curr->left);
	auto right = dfs(curr->right);
	if(left.first > right.first)return {left.first + 1, left.second};
	else if(left.first < right.first)return {right.first + 1, right.second};
	else return {left.first + 1, curr};
	}
	};

view raw Smallest Subtree with all the Deepest Nodes.cpp hosted with ❤ by GitHub