tr

tr
2个月前
class Solution {
public:
void connect(TreeLinkNode *root) {
while (root)
{
TreeLinkNode *tail = dummy;
while (root)
{
if (root->left)
{
tail->next = root->left;
tail = tail->next;
}
if (root->right)
{
tail->next = root->right;
tail = tail->next;
}
root = root->next;
}
tail->next = 0;
root = dummy->next;
}
}
};


tr
2个月前

(暴力搜索) O(5^n)

class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1 == s2) return true;
string ss1 = s1, ss2 = s2;
sort(ss1.begin(), ss1.end()), sort(ss2.begin(), ss2.end());
if (ss1 != ss2) return false;
for (int i = 1; i < s1.size(); i ++ )
{
if (isScramble(s1.substr(0, i), s2.substr(0, i))
&& isScramble(s1.substr(i), s2.substr(i)))
return true;
if (isScramble(s1.substr(0, i), s2.substr(s2.size() - i))
&& isScramble(s1.substr(i), s2.substr(0, s2.size() - i)))
return true;
}
return false;
}
};



tr
2个月前
class Solution {
public:
long long mx = INT_MIN;
int solve(TreeNode* root) {
if(root == NULL)
return 0;
int left = max(0, solve(root->left));
int right = max(0, solve(root->right));

mx = max(mx, (long long)root->val + left + right);
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
solve(root);
return mx;
}
};


tr
2个月前
class Solution {
public:
long long mx = INT_MIN;
int solve(TreeNode* root) {
if(root == NULL)
return 0;
int left = max(0, solve(root->left));
int right = max(0, solve(root->right));

mx = max(mx, (long long)root->val + left + right);
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
solve(root);
return mx;
}
};


tr
2个月前
class Solution {
public:
int ans;
int diameterOfBinaryTree(TreeNode* root) {
ans = 0;
depth(root);
return max(ans - 1, 0);
}
int depth(TreeNode* u)
{
if(!u) return 0;
int l = depth(u->left);
int r = depth(u->right);
ans = max(ans, l + r + 1);
return max(l, r) + 1;
}
};


tr
2个月前
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return NULL;
if(root == p || root == q) return root;
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
if(l && r) return root;
if(l) return l;
return r;
}
};


tr
2个月前
/**
* 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:

void inorder_traversal(TreeNode* node, vector<int>& nums)
{
if (node == nullptr)
return;

inorder_traversal(node->left, nums);
nums.push_back(node->val);
inorder_traversal(node->right, nums);
}

bool findTarget(TreeNode* root, int k) {

vector<int> nums;
inorder_traversal(root, nums);

int left = 0;
int right = nums.size() - 1;

while (left < right)
{
int sum = nums.at(left) + nums.at(right);
if (sum == k)
{
return true;
}
else if (sum > k)
{
--right;
}
else
{
++left;
}
}

return false;
}
};


tr
2个月前
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
if(!root) return ret;
queue<TreeNode*> q;
q.push(root);
while(q.size())
{
int len = q.size();
vector<int> tmp;
while(len--)
{
auto t = q.front(); q.pop();
tmp.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
ret.push_back(tmp);
}
return ret;
}
};


tr
2个月前
class Solution {
public:
string str;
int index = 0;
string next()
{
if(index >= str.length())
return "*";
int p = index;
while(p < str.length() && str[p] != ',')
p++;
int tmp = index;
index = p + 1;
return str.substr(tmp, index - tmp - 1);
}
bool valid()
{
string val = next();
if(val == "#")
return true;
if(val == "*")
return false;
return valid() && valid();
}
bool isValidSerialization(string preorder) {
str = preorder;
return valid() && index >= str.length();
}
};


tr
2个月前
/**
* 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:
unordered_map<int, int> in_index;
int pre_index = 0;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int in_st, int in_end)
{
if(in_st == in_end)
return NULL;

int root_val = preorder[pre_index++];
int index = in_index[root_val];

TreeNode* root = new TreeNode(root_val);

root->left = build(preorder, inorder, in_st, index);
root->right = build(preorder, inorder, index + 1, in_end);

return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i = 0; i < inorder.size(); i++) {
in_index[inorder[i]] = i;
}
return build(preorder, inorder, 0, inorder.size());
}
};