855学习记录数据结构树(2)二叉树拓展——炎泽汐$de$ Blog

文章目录[隐藏]

• 二叉树遍历的非递归实现
• 二叉树拓展

先序遍历

---

stack<TreeNode*> S;
void per(TreeNode* root){
    TreeNode* now = root;
    while(true){
        while(now){
            cout << now -> val << '\t';
            S.push(now -> right);
            now = now -> left; 
        }
        if(S.empty()){
            break;
        }
        now = S.top();
        S.pop();
    }
}

中序遍历

---

stack<TreeNode*> S;
void mid(TreeNode* root){
    TreeNode* now = root;
    while(true){
        while(now){
            S.push(now);
            now = now -> left; 
        }
        if(S.empty()){
            break;
        }
        now = S.top();
        S.pop();
        cout << now -> val << '\t';
        now = now -> right;
    }
}

后序遍历

---

      中右左翻转版本：

stack<TreeNode*> S;
void back(TreeNode* root){
    TreeNode* now = root;
    vector<int> result;
    if(!now){
        return;
    }
    S.push(now);
    while(!S.empty()){
        now = S.top();
        S.pop();
        result.push_back(now -> val);
        if(now -> left){
            S.push(now -> left);
        }
        if(now -> right){
            S.push(now -> right);
        }
    }
    reverse(result.begin(), result.end());
    for(auto it = result.begin(); it != result.end(); it++){
        cout << *it << '\t';
    }
}

      双指针版本：

stack<TreeNode*> s;
void back(TreeNode* root){
    if(root == nullptr){
        return;
    }
    TreeNode *cur = root;
    TreeNode *pre = nullptr;
    while(cur || !s.empty()){
    	while(cur){
            s.push(cur);
            cur = cur -> left;
        }
        cur = s.top();
        //没有右节点或者右节点已输出 
        if(cur -> right == nullptr || cur -> right == pre){
            cout << cur -> val << '\t';
            s.pop();
            pre = cur;
            cur = nullptr;
        }else{
            cur = cur -> right;
        }
    }
}

      23 真题静态链表版本：

struct{
    int Llink;
    char data;
    int Rlink;
}tree[n];
int s[n + 1];
int t = -1;
p = root;
while(p >= 0 || t >= 0){
    if(p >= 0){
        t = t + 1;
        s[t] = p + 1;//(1)
        p = tree[p].Llink;//(2)
    }else if(s[t] - 1 >= 0/*(3)*/){
        p = tree[s[t] - 1].Rlink;//(4)
        s[t] = -s[t];
    }else{
        cout << tree[-s[t] - 1].data << " ";//(5)
        t--;
    }
}

卡特兰数

---

      设$b_n$表示有$n$个节点的不同的二叉树棵数，当$n> 1$时可以通过递推关系得到：

$$
\begin{cases}
b_0=1& n=0\\
b_n=\sum_{i=0}^{n-1}{b_i\cdot b_{n-i-1},}& n>1\\
\end{cases}
$$

      同时可以通过生成函数推得：

$$
b_n=\frac{1}{n+1}C_{2n}^{n}=\frac{1}{n+1}\frac{\left( 2n \right) !}{n!\cdot n!}
$$

      它也是$n$个不同元素进栈出栈序列的个数。

int numTrees(int n) {
    int dp[n];
    memset(dp, 0, sizeof(dp));
    int k = 0;
    dp[0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1; j <= i; j++){
            dp[i] += dp[i - j] * dp[j - 1];
        }
    }
    return dp[n];
}

二叉树展开为链表

---

TreeNode* now = nullptr;
void flatten(TreeNode* root) {
    if(!root){
        return;
    }
    flatten(root -> right);
    flatten(root -> left);
    root -> right = now;
    root -> left = nullptr;
    now = root;
}

二叉树中的最大路径和

---

int ans;
int find(TreeNode* root) {
    if(!root){
        return 0;
    }else{
        int l = find(root -> left),r = find(root -> right);
        int a = max(l, 0) + max(r, 0) + root -> val;
        int b = root -> val + max(max(l, r), 0);
        ans = max(ans, max(a, b));
        return b;
    }
}
int maxPathSum(TreeNode* root) {
    ans = root -> val;
    find(root);
    return ans;
}

二叉树的最近公共祖先

---

      利用深搜找到通往两个目标节点的路径，从根开始对比两者路径，找到最后一个相同点即是解：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> a, b;
    dfs(root, p, a); dfs(root, q, b);
    TreeNode* ans = nullptr;
    for(int i = 0; i < min(a.size(), b.size()) && a[i] == b[i]; i++){
    	ans = a[i];
    }
    return ans;
}
bool dfs(TreeNode* cur, TreeNode* t, vector<TreeNode*>& path) {
    if(!cur){
    	return false;
    }
    path.push_back(cur);
    if(cur == t || dfs(cur->left, t, path) || dfs(cur->right, t, path)){
        return true;
    }else{
        path.pop_back();
        return false;
    }
}