958

Posted on In , Views:

題目:
https://leetcode.com/problems/check-completeness-of-a-binary-tree/

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
#define MAXN 105

TreeNode* q[MAXN]; // queue, bfs
int l, r;

class Solution {
public:
    // 判斷條件：
    // 1. 有右無左必為false
    // 2. 一旦遇到缺孩子的節點，接下來所有節點都必須是葉節點
    bool isCompleteTree(TreeNode* root) {
        if(root == nullptr) return true; // 題目認為空樹是complete binary tree

        l = r = 0;
        q[r++] = root;
        bool leaf = false;
        TreeNode* curr;
        while(l < r){
            curr = q[l++];
            if(curr->left == nullptr && curr->right != nullptr) return false; // 條件1
            if(leaf && (curr->left != nullptr && curr->right != nullptr)) return false; // 條件2

            if(curr->left != nullptr) q[r++] = curr->left;
            if(curr->right != nullptr) q[r++] = curr->right;

            if(curr->left == nullptr || curr->right == nullptr) leaf = true;
        }
        return true;
    }
};