lc366-Find Leaves of Binary Tree

發表於   |   分類於   |   0 comments   |  

recursively

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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 {
private:
    vector<vector<int>> res;
public:
    int findLevel(TreeNode* r) {
        if (r == nullptr) return 0;
        int level = 1+max(findLevel(r->left), findLevel(r->right));
        if (level > res.size()) res.push_back(vector<int>());
        if (r) res[level - 1].push_back(r->val);
        return level;
    }
    vector<vector<int>> findLeaves(TreeNode* root) {
        findLevel(root);
        return res;
    }
};

queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q1, q2;
        vector<vector<int>> res;
        if(root) q1.push(root);
        while (!q1.empty()) {
            vector<int> tmp_res;
            while (!q1.empty()) {
                TreeNode* t = q1.front();
                q1.pop();
                if (t->left) q2.push(t->left);
                if (t->right) q2.push(t->right);
                tmp_res.push_back(t->val);
            }
            swap(q1, q2);
            res.push_back(tmp_res);
        }
        return res;
    }
};