代码随想录算法训练营第十四天 | 144. 二叉树的前序遍历、94. 二叉树的序遍历、145. 二叉树的后序遍历、每日一题 1092. 最短公共序列

题目链接：

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

递归写法

前序

1.  
   class Solution {
2.  
   public:
3.  
   void dfs(TreeNode* cur, vector<int> &vec){
4.  
   if(cur == nullptr) return;
5.  
   vec.push_back(cur->val);
6.  
   dfs(cur->left, vec);
7.  
   dfs(cur->right, vec);
8.  
   }
9.  
    
10.  
    vector<int> preorderTraversal(TreeNode* root) {
11.  
    vector<int> ans;
12.  
    dfs(root, ans);
13.  
    return ans;
14.  
    }
15.  
    };

中序

1.  
   class Solution {
2.  
   public:
3.  
   void dfs(TreeNode* cur, vector<int> &vec){
4.  
   if(cur == nullptr) return;
5.  
   dfs(cur->left, vec);
6.  
   vec.push_back(cur->val);
7.  
   dfs(cur->right, vec);
8.  
   }
9.  
    
10.  
    vector<int> inorderTraversal(TreeNode* root) {
11.  
    vector<int> ans;
12.  
    dfs(root, ans);
13.  
    return ans;
14.  
    }
15.  
    };

后序

1.  
   class Solution {
2.  
   public:
3.  
   void dfs(TreeNode* node, vector<int> &ans) {
4.  
   if (node == nullptr) return;
5.  
   dfs(node->left, ans);
6.  
   dfs(node->right, ans);
7.  
   ans.emplace_back(node->val);
8.  
   }
9.  
    
10.  
    vector<int> postorderTraversal(TreeNode* root) {
11.  
    vector<int> ans;
12.  
    dfs(root, ans);
13.  
    return ans;
14.  
    }
15.  
    };

迭代写法

前序

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> preorderTraversal(TreeNode* root) {
4.  
   stack<TreeNode*> st;
5.  
   vector<int> ans;
6.  
   if (root == nullptr) return ans;
7.  
   st.push(root);
8.  
   while(!st.empty()){
9.  
   TreeNode* cur = st.top();
10.  
    st.pop();
11.  
    ans.push_back(cur->val);
12.  
    if(cur->right) st.push(cur->right);
13.  
    if(cur->left) st.push(cur->left);
14.  
    }
15.  
    return ans;
16.  
    }
17.  
    };

中序

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> inorderTraversal(TreeNode* root) {
4.  
   stack<TreeNode*> st;
5.  
   vector<int> ans;
6.  
   TreeNode* cur = root;
7.  
   while(cur != nullptr || !st.empty()){
8.  
   if(cur != nullptr){
9.  
   st.push(cur);
10.  
    cur = cur->left;
11.  
    }else {
12.  
    cur = st.top();
13.  
    st.pop();
14.  
    ans.push_back(cur->val);
15.  
    cur = cur->right;
16.  
    }
17.  
    }
18.  
    return ans;
19.  
    }
20.  
    };

后序

利用一个标记位来实现

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> postorderTraversal(TreeNode* root) {
4.  
   vector<int> result;
5.  
   stack<pair<TreeNode*, int>> st;
6.  
   if (root != NULL) st.push({root, 0});
7.  
   while (!st.empty()) {
8.  
   int& flag = st.top().second;
9.  
   TreeNode* cur = st.top().first;
10.  
    if (!flag) {
11.  
    flag = 1;
12.  
    if(cur->right) st.push({cur->right, 0});
13.  
    if(cur->left) st.push({cur->left, 0});
14.  
    } else {
15.  
    result.emplace_back(cur->val);
16.  
    st.pop();
17.  
    }
18.  
    }
19.  
    return result;
20.  
    }
21.  
    };

1092. 最短公共超序列

最长公共子序列的加强题，前半部分动态规划求解一样的代码

后半部分根据状态数组，迭代构造答案

1.  
   class Solution {
2.  
   public:
3.  
   string shortestCommonSupersequence(string &s, string &t) {
4.  
   int n = s.size(), m = t.size();
5.  
   vector<vector<int>> f(n 1, vector<int>(m 1, 0));
6.  
   for (int j = 1; j <= m; j ) f[0][j] = j;
7.  
   for (int i = 1; i <= n; i ) f[i][0] = i;
8.  
   for (int i = 0; i < n; i ) {
9.  
   for (int j = 0; j < m; j ) {
10.  
    if (s[i] == t[j])
11.  
    f[i 1][j 1] = f[i][j] 1;
12.  
    else
13.  
    f[i 1][j 1] = min(f[i][j 1], f[i 1][j]) 1;
14.  
    }
15.  
    }
16.  
    string ans;
17.  
    int i = n - 1, j = m - 1;
18.  
    while (i >= 0 && j >= 0) {
19.  
    if (s[i] == t[j]) {
20.  
    ans = s[i];
21.  
    --i;
22.  
    --j;
23.  
    } else if (f[i 1][j 1] == f[i][j 1] 1){
24.  
    ans = s[i--];
25.  
    } else {
26.  
    ans = t[j--];
27.  
    }
28.  
    }
29.  
    reverse(ans.begin(), ans.end());
30.  
    return s.substr(0, i 1) t.substr(0, j 1) ans;
31.  
    }
32.  
    };

这篇好文章是转载于：学新通技术网