专题: 二叉树题目总结-二

作者 Lucyyang 日期 2020-03-16
专题: 二叉树题目总结-二

"争取每一天的成功,避免以失败收场。"

树的子结构

Subtree of Another Tree

题目:L572,判断一棵树的是否为另一个棵树的子树。

方法1:我自己的方法是,找到任意一个值相同的根,然后check是否为same tree。将所有与root2->val相同的节点都保存在vector中。代码比较冗长一些。

代码:

class Solution {
public:
vector<TreeNode*> tmp;
void findhead(TreeNode* root, int val) {
if(root == NULL)
return;
// printf("root->val=%d\n",root->val);
if(root->val == val)
tmp.push_back(root);
findhead(root->left, val);
findhead(root->right, val);
}
bool judgetree(TreeNode* r1, TreeNode* r2) {
if(r1 == NULL && r2 == NULL)
return true;
else if(r1 == NULL || r2 == NULL)
return false;
return (r1->val == r2->val) && judgetree(r1->left, r2->left) && judgetree(r1->right, r2->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
findhead(s, t->val);
// printf("%d\n",shead->val);
bool ans = false;
for(auto i:tmp){
ans = ans||judgetree(i, t);
}
return ans;
}
};

Count Univalue Subtrees

题目:LC250,计算所有节点数值都相同的子树个数,注意叶子结点也算一个。

方法:分别对左右子树进行判断:如果左子树的val与根节点相同并且左子树的subtree也是univalue subtree,则左子树为univalue subtree;如果根节点和右节点值相同并且右子树也是相同值的univalue subtree,则右子树为univalue subtree。如果左右子树都返回为true,则该根节点为univalue subtree。

代码:

class Solution {
public:
int res = 0;
bool isUnival(TreeNode* root) {
if(root->left == NULL && root->right == NULL){
res++;
return true;
}
bool is_uni = true;
if(root->left)
is_uni = isUnival(root->left)&&root->left->val == root->val;
if(root->right)
is_uni = isUnival(root->right)&&is_uni&&root->right->val == root->val;
if(is_uni)
res++;
return is_uni;
}
int countUnivalSubtrees(TreeNode* root) {
if(root == NULL)
return 0;
isUnival(root);
return res;
}
};

Largest BST Subtree

题目:LC333,找出二叉树中,节点最多的二叉搜索子树。

方法:递归解法返回一个vector<int>,存储三个元素,分别是包含该节点的最小值,包含该节点的最大值,当前最多的二叉搜索子树节点个数。首先返回左右子树的vector<int>数组,分别比较当前值和左子树最大值,右子树最小值的范围;如果在此范围之内,将结果更新为包含该节点在内的最小值,包含该节点在内的最大值以及加上该节点的值。如果不在这个范围之内,更新为最小值,最大值和左右子树中最多的节点树。注意,当节点不存在时,分别返回最大值,最小值和0,这是为了保证叶子节点能在这个范围内。

代码:

class Solution {
public:
int largestBSTSubtree(TreeNode* root) {
vector<int> res = helper(root);
return res[2];
}
vector<int> helper(TreeNode* node) {
if (!node) return {INT_MAX, INT_MIN, 0};
vector<int> left = helper(node->left), right = helper(node->right);
if (node->val > left[1] && node->val < right[0]) {
return {min(node->val, left[0]), max(node->val, right[1]), left[2] + right[2] + 1};
} else {
return {INT_MIN, INT_MAX, max(left[2], right[2])};
}
}
};