Complete Binary Tree (Ladder)

Description

Check a binary tree is completed or not. A complete binary tree is a binary tree that every level is completed filled except the deepest level. In the deepest level, all nodes must be as left as possible. See more definition

Example:

    1
   / \
  2   3
 /
4

is a complete binary.

    1
   / \
  2   3
   \
    4

is not a complete binary.

Challenge:
Do it in O(n) time

Link

Lintcode_ladder

Method

1. Find all nodes(valid or nullptr), then delete all nullptr nodes from back. Finally. check whether any nullptr node exists.
2. x

Example

1. 1

   /**
   * Definition of TreeNode:
   * class TreeNode {
   * public:
   *     int val;
   *     TreeNode *left, *right;
   *     TreeNode(int val) {
   *         this->val = val;
   *         this->left = this->right = NULL;
   *     }
   * }
   */
   class Solution {
   public:
    /**
     * @param root, the root of binary tree.
     * @return true if it is a complete binary tree, or false.
     */
    bool isComplete(TreeNode* root) {
        // Write your code here
        if (!root) {
            return true;
        }
        vector<TreeNode*> nodes;
        // get all nodes
        nodes.push_back(root);
        for (int i = 0; i < nodes.size(); ++i) {
            TreeNode* cur = nodes[i];
            if (!cur) {
                continue;
            }
            nodes.push_back(cur->left);
            nodes.push_back(cur->right);
        }
        // find and pop_back any nullptr node
        while (nodes.size() > 0 && !nodes[nodes.size()-1]) {
            nodes.pop_back();
        }
        // if all nodes are nullptr
        if (nodes.empty()) {
            return true;
        }
        // also we can ignore the last element of the nodes
        // because the last one we have tested before
        // like : for (int i = 0; i + 1 < nodes.size(); ++i) {}
        for (int i = 0; i < nodes.size(); ++i ) {
            if (!nodes[i]) {
                return false;
            }
        }
        return true;
    }
   };
   

Similar problems

x

Tags

x