The 17th day of the special assault version of the sword offer

剑指 Offer II 050. 向下的路径节点之和

容易想到$O(N^2)$brute force traversal algorithm,本质上跟forDouble-loop brute force traversal is similar,That is, the skills required to implement the code are more and more novel.

class Solution {
    
public:
	//保证rootEach node in each of the following paths is picked,There will be no unselected nodes in the middle of the path
    int dfs(TreeNode *root, int targetSum) {
     
        if(!root) return 0;
        int cnt = 0;
        if(root->val == targetSum) cnt++;
        cnt += dfs(root->left, targetSum - root->val);
        cnt += dfs(root->right, targetSum - root->val);
        return cnt;
    }

    int pathSum(TreeNode* root, int targetSum) {
    
        if(!root) return 0;
        //选取root点
        int ans = dfs(root,targetSum);
        //不选root点 
        ans += pathSum(root->left, targetSum);
        ans += pathSum(root->right, targetSum);
        return ans;
    }
};

仔细思考会发现,There is a lot of double counting here,You can use prefix sums to optimize into $O(N)$ 时间复杂度,where the prefix and value are placedmap的键上,The value is the number,This eliminates the need to re-traverse the previous prefix sum,Strictly speaking, because it is usedmapThis results in an algorithmic complexity of $O(N\ast logN)$.

class Solution {
    
private:
    unordered_map<long long, int> prefix;
    // int ans = 0; 
public:
    int dfs(TreeNode *root, long long sum, int targetSum) {
    
        if(!root) return 0;
        sum += root->val;
        int ans = 0;
        if(prefix.count(sum-targetSum)) {
     //sum - x = targetSum,其中xIt is a prefix sum in front of it
            ans += prefix[sum-targetSum];
        }
        prefix[sum]++;
        ans += dfs(root->left, sum, targetSum);
        ans += dfs(root->right, sum, targetSum);
        prefix[sum]--; //回溯,Otherwise, the sum of the nodes of other branches will be used
        return ans;
    }

    int pathSum(TreeNode* root, int targetSum) {
    
        prefix[0] = 1; //什么都没选,when arootThe sum of the starting path nodes is equal to targetSum时会用到
        return dfs(root, 0, targetSum);
    }
};

---

剑指 Offer II 051. 节点之和最大的路径

Use post-order traversal+DP思想

• Post-order traversal is to first find the maximum value of the left and right subpaths
• DPThe idea is that the current stack frame will calculate the current node+Left subpath+Right subpath（This cannot be backtracked to the parent node,Because the path is not linear）,No matter what you want to backtrack to the parent node to the current node、当前+Left subpath、当前+Right subpath,The final result is the global maximum path sum.

class Solution {
    
private:
    int res = INT_MIN;    
public:
    int maxPathSum(TreeNode* root) {
    
        maxGain(root);
        return res;
    }

    int maxGain(TreeNode *root) {
    
        if(root == nullptr) return 0;
        int left = maxGain(root->left);
        int right = maxGain(root->right);
        res = max(res, root->val); //Consider both the left and right paths to be negative
        res = max(res, root->val + left);
        res = max(res, root->val + right);
        res = max(res, root->val + left + right);
        //Backtracking can only return the current node value 或 当前+左 或 当前+右
        return max(max(root->val,root->val+left), root->val+right);
    }
};

代码简化版,It is better not to select when left and right are negative values,就为0

class Solution {
    
private:
    int res = INT_MIN;    
public:
    int maxPathSum(TreeNode* root) {
    
        maxGain(root);
        return res;
    }

    int maxGain(TreeNode *root) {
    
        if(root == nullptr) return 0;
        //It is better not to select when left and right are negative values,就为0
        int left = max(0,maxGain(root->left)); 
        int right = max(0,maxGain(root->right));
        res = max(res, root->val + left + right);
        //Backtracking can only return the current node value 或 当前+左 或 当前+右
        return max(left,right) + root->val;
    }
};

---

剑指 Offer II 052. 展平二叉搜索树

最容易想到的方法,Save the in-order traversal sequence first,Then specify the right node of each node in sequence order,This is equivalent to creating a linked list

class Solution {
    
public:
    void inorder(vector<TreeNode*> &ls, TreeNode *root) {
    
        if(!root) return;
        inorder(ls,root->left);
        ls.emplace_back(root);
        inorder(ls,root->right);
    }   
    TreeNode* increasingBST(TreeNode* root) {
    
        vector<TreeNode*> ls;
        inorder(ls,root);
        auto head = new TreeNode(-1);
        auto tmp = head;
        for(auto cur: ls) {
    
            cur->left = cur->right = nullptr;
            tmp->right = cur;
            tmp = cur;
        }
        return head->right;
    }
};

Come up with a harder way,Change the direction of the node pointer while traversing.Grab the inorder traversal algorithm->Traversal order invariant features.Then follow the traversal order with a move pointer.（有个坑,Move pointers cannot be placed in function parameters,A global variable is required,Because of the recursive backtracking process,Moving the pointer is still the same as it was and didn't change）

class Solution {
    
private:
    TreeNode *cur = nullptr;    
public:
    void inorder(TreeNode *root) {
    
        if(!root) return;
        inorder(root->left);
        root->left = nullptr;
        cur->right = root;
        cur = cur->right;
        inorder(root->right);
    }   
    TreeNode* increasingBST(TreeNode* root) {
    
        auto head = new TreeNode(-1);
        cur = head;
        inorder(root);
        return head->right;
    }
};