WRY

Where Are You?
You are on the brave land,
To experience, to remember...

0%

算法随记 【2024年02月】

Posted on Edited on In
随手做的算法题

练习收获

二叉树的遍历方法

  • 后序遍历
  • 层级遍历

满二叉树的编码特性

  • 所有节点编码从1开始编码
  • 每层节点从零开始编码

练习题目

590. N-ary Tree Postorder Traversal

Version 1

递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void go(Node* root, vector<int> & ans){
        for(int i=0;i<root->children.size();++i) go(root->children[i], ans);
        ans.push_back(root->val);
    }
    vector<int> postorder(Node* root) {
        vector<int> ans;
        if(!root) return ans;
        go(root, ans);
        return ans;
    }
};

662. Maximum Width of Binary Tree

Version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        queue<pair<TreeNode*, pair<unsigned int, unsigned int>>> que; // TreeNode*, level, index
        if(!root) return 0;
        unsigned int ans = 1, level = 0, curl, curi, li=0;
        que.push(pair(root, pair(0, 0)));
        while(!que.empty()) {
            root = que.front().first;
            curl = que.front().second.first;
            curi = que.front().second.second;
            que.pop();
            if(curl!=level){
                ++level, li=curi;
            }
            if(root->left) que.push(pair(root->left, pair(level+1, curi*2)));
            if(root->right) que.push(pair(root->right, pair(level+1, curi*2+1)));
            if(root) ans=max(curi-li+1, ans);
            // cout<<root->val<<" "<<curi<<" "<<ans<<endl;
        }
        return ans;
    }
};