leetcode 865. 具有所有最深节点的最小子树

本文主要是介绍leetcode 865. 具有所有最深节点的最小子树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路

递归判断条件：

1. 如果左子树和右子树的高相等，说明当前root的这棵树就是答案
2. 如果左子树比右子树高，那么说明root和右子树的所有结点都不是答案，遍历左子树继续找
3. 如果右子树比左子树高，那么说明root和左子树的所有结点都不是答案，遍历右子树继续找

代码

class Solution {
public:TreeNode* subtreeWithAllDeepest(TreeNode* root) {if(!root)return NULL;int left_height = getHeight(root->left);int right_height = getHeight(root->right);if(left_height == right_height)return root;if(left_height > right_height)return subtreeWithAllDeepest(root->left);return subtreeWithAllDeepest(root->right);}// 通过DFS得到树的高int getHeight(TreeNode* root){if(!root){return 0;}int left = getHeight(root->left);int right = getHeight(root->right);return max(left, right)+1;}};

这篇关于leetcode 865. 具有所有最深节点的最小子树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---