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

以你之姓@ 2023-07-16 09:56 55阅读 0赞
  1. 路径总和2
    给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

本题和上题的区别在于需要记录所有路径，因此在递归函数中加上一个记录当前路径的数组，满足则输出

  1. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  2. class Solution { 
  3.     vector<vector<int>> ret;
  4.     vector<int> tmp;
  5. public:
  6.     vector<vector<int>> pathSum(TreeNode* root, int sum) { 
  7.         pathSearch(root, sum, tmp);
  8.         return ret;
  9.     }   
  11.     void pathSearch(TreeNode *root, int sum, vector<int> tmp)
  12.     { 
  13.         if (root == NULL)        
  14.             return;
  16.         sum -= root->val;
  17.         tmp.push_back(root->val);
  19.         if (root->left == NULL & root->right == NULL)
  20.         { 
  21.             if (sum == 0)
  22.             { 
  23.                 ret.push_back(tmp);
  24.                 tmp.clear();
  25.             }
  26.             else tmp.clear();
  27.             return;
  28.         }
  30.         pathSearch(root->left, sum, tmp);
  31.         pathSearch(root->right, sum, tmp);
  32.     }
  33. };
  1. 二叉树展开为链表
    给定一个二叉树，原地将它展开为链表。

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

  1. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  3. TreeNode* last = nullptr;
  4. class Solution { 
  5. public:
  6.     void flatten(TreeNode* root) { 
  7.         if (root == nullptr) return;
  8.         flatten(root->left);
  9.         flatten(root->right);
  10.         if (root->left != nullptr) { 
  11.             auto pre = root->left;
  12.             while (pre->right != nullptr) pre = pre->right;
  13.             pre->right = root->right;
  14.             root->right = root->left;
  15.             root->left = nullptr;
  16.         }
  17.         root = root->right;
  18.         return;
  19.     }
  20. };
  22. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  23. class Solution { 
  24. public:
  25.     void flatten(TreeNode* root) { 
  26.         while (root != nullptr) { 
  27.             if (root->left != nullptr) { 
  28.                 auto most_right = root->left; // 如果左子树不为空, 那么就先找到左子树的最右节点
  29.                 while (most_right->right != nullptr) most_right = most_right->right; // 找最右节点
  30.                 most_right->right = root->right; // 然后将跟的右孩子放到最右节点的右子树上
  31.                 root->right = root->left; // 这时候跟的右孩子可以释放, 因此我令左孩子放到右孩子上
  32.                 root->left = nullptr; // 将左孩子置为空
  33.             }
  34.             root = root->right; // 继续下一个节点
  35.         }
  36.         return;
  37.     }
  38. };

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

    // 一维DP
    int numDistinct(string s, string t) { 

    1. int s_size = s.size(), t_size = t.size();
    2. vector<long> dp(s_size + 1, 1);
    3. for (auto c : t) { 
    4.     auto last = dp[0]; // 记录上一个值
    5.     dp[0] = 0;
    6.     for (int j = 0; j < s_size; ++j) { 
    7.         auto record = dp[j+1];
    8.         if (s[j] == c) dp[j+1] = last + dp[j];
    9.         else dp[j+1] = dp[j];
    10.         last = record;
    11.     }
    12. }
    13. return dp.back();

    }

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

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

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

  1. /* // 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) {} }; */
  2. class Solution { 
  3. public:
  4.     Node* connect(Node* root) { 
  5.         if (root == NULL)
  6.             return NULL;
  7.         root->next = NULL;
  8.         connectRight(root, root);
  9.         return root;
  10.     }
  12.     void connectRight(Node *root, Node *paraent)
  13.     { 
  14.         if (root == NULL)
  15.             return;
  17.         if (root == paraent->left)
  18.             root->next = paraent->right;
  19.         else if (paraent->next != NULL)
  20.             root->next = paraent->next->left;
  21.         connectRight(root->left, root);
  22.         connectRight(root->right, root);
  23.     }
  24. };
  1. 填充每个节点的下一个右侧节点2
    本题和上题的区别在于不保证是完美二叉树。

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

  1. /* // 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) {} }; */
  2. class Solution { 
  3. public:
  4.     Node* connect(Node* root) 
  5.     { 
  6.         Node *headParent = root;
  7.         while (headParent != NULL)
  8.         { 
  9.             // 获得队首节点的父节点
  10.             while (headParent && headParent->left == NULL && headParent->right == NULL)
  11.                 headParent = headParent->next;
  13.             if (headParent == NULL)
  14.                 break;
  16.             Node *cur = NULL, *tmp = headParent;
  18.             // 广度优先遍历该层
  19.             while (tmp)
  20.             { 
  21.                 if (tmp -> left)
  22.                 { 
  23.                     if (cur != NULL)
  24.                     { 
  25.                         cur->next = tmp->left;
  26.                     }
  27.                     cur = tmp->left;
  28.                 }
  29.                 if (tmp -> right)
  30.                 { 
  31.                     if (cur != NULL)
  32.                     { 
  33.                         cur->next = tmp->right;
  34.                     }
  35.                     cur = tmp->right;
  36.                 }
  37.                 tmp = tmp->next;
  38.             }         
  40.             // 进入下一级
  41.             headParent = headParent->left ? headParent->left : headParent->right;
  42.         }
  43.         return root;
  44.     }
  45. };
  1. 杨辉三角
    给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

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

  1. class Solution { 
  2. public:
  3.     vector<vector<int>> generate(int numRows) { 
  4.         vector<vector<int>> dp(numRows);
  6.         for (int i = 0; i < numRows; i++)
  7.         { 
  8.             dp[i].resize(i + 1);
  9.             dp[i][0] = 1;
  10.             dp[i][i] = 1;
  11.         }
  13.         for (int i = 2; i < numRows; i++)
  14.         { 
  15.             for (int j = 1; j < i; j++)
  16.             { 
  17.                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  18.             }
  19.         }
  21.         return dp;
  22.     }
  23. };
  1. 杨辉三角2
    和上题的区别在于只返回第n行

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

  1. class Solution { 
  2. public:
  3.     vector<int> getRow(int rowIndex) { 
  4.         vector<int> ret(rowIndex + 1);
  5.         vector<int> last(rowIndex);
  7.         for (int j = 0; j <= rowIndex; j++)
  8.         {    
  9.             ret[0] = 1;
  10.             ret[j] = 1;
  11.             last = ret;
  12.             for (int i = 1; i < j; i++)
  13.                 ret[i] = last[i - 1] + last[i];
  14.         }
  16.         return ret;
  18.     }
  19. };

发表评论

表情：
评论列表 （有 0 条评论，55人围观）

还没有评论，来说两句吧...

相关阅读