剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
对于二叉搜索树而言,因为其特殊的结构,即左子树的值均小于root的值,右子树的值均大于root的值,因此,对于二叉搜索树的最近公共祖先比较好确定。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return root;
if(p->val == root->val || q->val == root->val)//如果p和q其中一个等于root 那么root即为最近公共祖先
{
return root;
}
if(p->val < root->val && q->val < root->val)// 如果p和q的值都小于root的值那么去root的左子树去寻找
{
return lowestCommonAncestor(root->left, p, q);
}
else if(p->val > root->val && q->val > root->val)// 如果p和q的值都大于root的值那么去root的右边子树去寻找
{
return lowestCommonAncestor(root->right, p, q);
}
else //此时说明 p和q位于root的左右两侧
{
return root;
}
}
};
剑指 Offer 68 - II. 二叉树的最近公共祖先
二叉树不像二叉搜索树那样结构与数值大小强相关。因此,不同通过判断p->val q->val和root->val的值的关系去选择去root->left或者root->right找最近公共祖先,只能分别试着去root->left或者root->right找最近公共祖先,如果其中一个为空,则返回另一个,如果两个都为空 返回空,如果两个均不为空,那么返回此时的root
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return root;
if(p->val == root->val || q->val == root->val) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(!left) return right;
else if(!right) return left;
else return root;
}
};
leetcode?662. 二叉树最大宽度
思路:利用满二叉树? BFS
?我们可以把这些值存在原来的节点中,也可以新建一个map来保存这些值。
并利用双端队列deque
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
int len = 0;
deque<TreeNode*> a;
root->val = 1;
a.push_back(root);
while(!a.empty())
{
int size = a.size();
len = max(len, a.back()->val - a.front()->val + 1);
// 编号缩小的差值
int offset = a.front()->val;//为了防止节点中的val过大
//二叉树中每一行的第一个节点中的值,作为参考值 去计算后面节点的值
while(size--)
{
TreeNode* temp = a.front();
temp->val -= offset;
a.pop_front();
if(temp->left)
{
a.push_back(temp->left);
temp->left->val = 2 * temp->val;
}
if(temp->right)
{
a.push_back(temp->right);
temp->right->val = 2 * temp->val + 1;
}
}
}
return len;
}
};
剑指 Offer 54. 二叉搜索树的第k大节点
思路:采用右--中--左的遍历方式
注意:count++之后立即进行判断是否是第k大的数? count记录第count个大的值
class Solution {
int res = 0;
void dfs(TreeNode* root, int k, int &count)
{
if(!root) return;
if(root->right) dfs(root->right, k, count);
count++;
if(count == k)
{
res = root->val;
return;
}
if(root->left) dfs(root->left,k, count);
}
public:
int kthLargest(TreeNode* root, int k) {
if(!root) return 0;
int count = 0;
dfs(root, k, count);
return res;
}
};
leetcode?230. 二叉搜索树中第K小的元素
思路:同上
class Solution {
int res = 0;
void dfs(TreeNode* root, int k, int& count)
{
if(!root) return;
dfs(root->left, k , count);
count++;
if(count == k)
{
res = root->val;
return;
}
dfs(root->right, k , count);
}
public:
int kthSmallest(TreeNode* root, int k) {
if(!root) return 0;
int count = 0;
dfs(root, k ,count);
return res;
}
};
剑指 Offer 55 - II. 平衡二叉树
思路:根据求二叉树的最大深度 只需要加个比较 left和right的差值
class Solution {
bool res = true;
int dfs(TreeNode *root)
{
if(!root) return 0;
int left = dfs(root->left);
int right = dfs(root->right);
if(abs(left - right) > 1)
{
res = false;
return 0;
}
return max(left, right) + 1;
}
public:
bool isBalanced(TreeNode* root) {
dfs(root);
return res;
}
};
|