头像

开水白菜




离线:2小时前



开水白菜
2小时前

思路

  1. 前序遍历,先找set中有没有适合当前节的。
  2. 如果没有,则把当前节点加入set
  3. 遍历左子树和右子树,或 连接,因为只要满足一对就可以
  4. 节点是逐个加入的,2+6 = 8 的情况是,如果2先加入,可能匹配不上,但是等之后4加入以后,就能匹配上了

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        set<int> st;
        return find(root,k,st);
    }
    bool find(TreeNode* root ,int k,set<int>& st){
        if(root == nullptr) return false;
        if(st.find(k-root->val)!=st.end())return true;
        st.insert(root->val);
        return find(root->left,k,st) || find(root->right,k,st);
    }
};



/**
 * 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* pre;
    TreeNode* dumpy;
    TreeNode* convertBiNode(TreeNode* root) {
        pre = new TreeNode(-1);
        dumpy = pre;
        inorder(root);
        return dumpy->right;
    }
    void inorder(TreeNode* root){
        if(root == NULL) return ;
        inorder(root->left);
        pre->right = root;
        root->left = nullptr;
        pre = root;
        inorder(root->right);
    }
};



/**
 * 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:
    int getMinimumDifference(TreeNode* root) {
        int ans = INT_MAX,pre = -1;
        inorder(root,pre,ans);
        return ans;
    }
    void inorder(TreeNode* root, int& pre, int& ans){
        if(root == NULL) return ;
        inorder(root->left,pre,ans);
        if(pre == -1) pre = root->val;
        else {
            ans = min(ans,root->val - pre);
            pre = root->val;
        }
        inorder(root->right,pre,ans);
    }
};

中序遍历为升序序列,不断比较pre和cur就可以




/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int tilt = 0;
    int findTilt(TreeNode* root) {
        dfs(root);
        return tilt;
    }
    int dfs(TreeNode* root){
        if(root == nullptr) return 0 ;
        int left = dfs(root->left);
        int right = dfs(root->right);
        tilt += abs(left-right);
        return root->val+left+right;
    }
};

二叉树的坡度就是各个节点的坡度之和




/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> res1;
        vector<int> res2;
        find_leaf(root1,res1);
        find_leaf(root2,res2);
        return res1 == res2;
    }
    void find_leaf(TreeNode* root,vector<int>& res){
        if(root == nullptr) return ;
        if(root->left == nullptr && root->right == nullptr) res.emplace_back(root->val);
        find_leaf(root->left,res);
        find_leaf(root->right,res);
    }
};




题目

任意节点到另一任意节点的路径的权值最大是多少

思路

  1. 如果当前节点的左右能连起来,则为node->left + node + node->right
  2. 如果连不起来,返回给当前节点的父节点 node + max(left,right)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int max_sum = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return max_sum;
    }
    int dfs(TreeNode* root){
        if(root == nullptr ) return 0 ;
        int left = max(0,dfs(root->left));
        int right = max(0,dfs(root->right));
        max_sum = max(max_sum,root->val + left + right);
        int ret = max(left,right) + root->val;
        return ret;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string s;
        dfs(root,s,res);
        return res;

    }
    void dfs(TreeNode* root, string s, vector<string>& res){
        if(root == nullptr){ 
            return;
        }
        else s+=to_string(root->val);
        if(root->left && root->right ){
            s+="->";
            dfs(root->left,s,res);
            dfs(root->right,s,res);    
        }
        else if(root->left || root->right){
            s+="->";
            if(root->left) dfs(root->left,s,res);
            if(root->right) dfs(root->right,s,res);
        } 
        else res.emplace_back(s);
    }
};



思路

  1. 把root的值*2加到左右孩子节点上
  2. 1e9+7 会被当成浮点数,要完整写出来,不知道为什么
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        if(root == nullptr) return 0;
        int mod = root->val % (1000000007);
        if(root->left == nullptr && root->right == nullptr) return mod;
        if(root->left != nullptr) root->left->val += mod << 1;
        if(root->right != nullptr) root->right->val += mod << 1;
        return (sumRootToLeaf(root->left) + sumRootToLeaf(root->right)) % (1000000007);
    }
};



/**
 * 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:
    bool isUnivalTree(TreeNode* root) {
        if(root == NULL) return true;
        else if(root->left && root->left->val != root->val) return false;
        else if(root->right && root->right->val != root->val) return false;
        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
};



思路

  1. 三个数的最大乘积要么是最大的三个数,要么是最小的两个负数乘最大整数
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size() -1 ;
        return max(nums[0]*nums[1]*nums[n],nums[n-2]*nums[n-1]*nums[n]);
    }
};