leetcode解题思路分析（十七）113 - 119题

以你之姓@ 2023-07-16 09:56 23阅读 0赞

1.  路径总和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 { 
        vector<vector<int>> ret;
        vector<int> tmp;
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) { 
            pathSearch(root, sum, tmp);
            return ret;
        }   
    
        void pathSearch(TreeNode *root, int sum, vector<int> tmp)
        { 
            if (root == NULL)        
                return;
            
            sum -= root->val;
            tmp.push_back(root->val);
    
            if (root->left == NULL & root->right == NULL)
            { 
                if (sum == 0)
                { 
                    ret.push_back(tmp);
                    tmp.clear();
                }
                else tmp.clear();
                return;
            }
    
            pathSearch(root->left, sum, tmp);
            pathSearch(root->right, sum, tmp);
        }
    };

1.  二叉树展开为链表  
    给定一个二叉树，原地将它展开为链表。

**本题做法类似于莫里斯遍历，可采用递归或者非递归做。推荐非递归，性能非常优秀**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    
    TreeNode* last = nullptr;
    class Solution { 
    public:
        void flatten(TreeNode* root) { 
            if (root == nullptr) return;
            flatten(root->left);
            flatten(root->right);
            if (root->left != nullptr) { 
                auto pre = root->left;
                while (pre->right != nullptr) pre = pre->right;
                pre->right = root->right;
                root->right = root->left;
                root->left = nullptr;
            }
            root = root->right;
            return;
        }
    };

/** * 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 flatten(TreeNode* root) { 
            while (root != nullptr) { 
                if (root->left != nullptr) { 
                    auto most_right = root->left; // 如果左子树不为空, 那么就先找到左子树的最右节点
                    while (most_right->right != nullptr) most_right = most_right->right; // 找最右节点
                    most_right->right = root->right; // 然后将跟的右孩子放到最右节点的右子树上
                    root->right = root->left; // 这时候跟的右孩子可以释放, 因此我令左孩子放到右孩子上
                    root->left = nullptr; // 将左孩子置为空
                }
                root = root->right; // 继续下一个节点
            }
            return;
        }
    };

1.  不同的子序列  
    给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。  
    一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

// 一维DP
    int numDistinct(string s, string t) { 
        int s_size = s.size(), t_size = t.size();
        vector<long> dp(s_size + 1, 1);
        for (auto c : t) { 
            auto last = dp[0]; // 记录上一个值
            dp[0] = 0;
            for (int j = 0; j < s_size; ++j) { 
                auto record = dp[j+1];
                if (s[j] == c) dp[j+1] = last + dp[j];
                else dp[j+1] = dp[j];
                last = record;
            }
        }
        return dp.back();
    }

1.  填充每个节点的下一个右侧节点指针  
    给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node \{  
int val;  
Node \*left;  
Node \*right;  
Node \*next;  
\}  
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

**本题其实是将一个普通的树转化为了B树，方法在于对每个节点增加平级链接，主要有两个逻辑点：  
左儿子连接右儿子  
右儿子连接父亲的next的左儿子  
根据这两点写代码即可**

1.  填充每个节点的下一个右侧节点2  
    本题和上题的区别在于不保证是完美二叉树。

**本题不可采取深度优先，因为可能存在某些子节点为空，需要next连接到尚未完成的父节点的后续节点。采取广度优先可以轻松解决，每次遍历该层，然后再去处理下一层。**

/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */
    class Solution { 
    public:
        Node* connect(Node* root) 
        { 
            Node *headParent = root;
            while (headParent != NULL)
            { 
                // 获得队首节点的父节点
                while (headParent && headParent->left == NULL && headParent->right == NULL)
                    headParent = headParent->next;
    
                if (headParent == NULL)
                    break;
    
                Node *cur = NULL, *tmp = headParent;
    
                // 广度优先遍历该层
                while (tmp)
                { 
                    if (tmp -> left)
                    { 
                        if (cur != NULL)
                        { 
                            cur->next = tmp->left;
                        }
                        cur = tmp->left;
                    }
                    if (tmp -> right)
                    { 
                        if (cur != NULL)
                        { 
                            cur->next = tmp->right;
                        }
                        cur = tmp->right;
                    }
                    tmp = tmp->next;
                }         
    
                // 进入下一级
                headParent = headParent->left ? headParent->left : headParent->right;
            }
            return root;
        }
    };

1.  杨辉三角  
    给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

**很简单的动态规划，公式为`dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]`**

class Solution { 
    public:
        vector<vector<int>> generate(int numRows) { 
            vector<vector<int>> dp(numRows);
            
            for (int i = 0; i < numRows; i++)
            { 
                dp[i].resize(i + 1);
                dp[i][0] = 1;
                dp[i][i] = 1;
            }
    
            for (int i = 2; i < numRows; i++)
            { 
                for (int j = 1; j < i; j++)
                { 
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
    
            return dp;
        }
    };

1.  杨辉三角2  
    和上题的区别在于只返回第n行

**动态规划的降维：其实只依赖于上一行，因此可以降维到一维dp**

class Solution { 
    public:
        vector<int> getRow(int rowIndex) { 
            vector<int> ret(rowIndex + 1);
            vector<int> last(rowIndex);
    
            for (int j = 0; j <= rowIndex; j++)
            {    
                ret[0] = 1;
                ret[j] = 1;
                last = ret;
                for (int i = 1; i < j; i++)
                    ret[i] = last[i - 1] + last[i];
            }
    
            return ret;
    
        }
    };