花花酱 LeetCode 958. Check Completeness of a Binary Tree

By zxi on December 18, 2018

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

Solution:

Level order traversal, if any nodes appears after a missing node then the tree is not a perfect binary tree.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isCompleteTree(TreeNode* root) {

if (!root) return true;

queue<TreeNode> q;

q.push(root);

bool missing = false;

while (!q.empty()) {

auto size = q.size();

while (size--) {

auto node = q.front(); q.pop();

if (node) {

if (missing) return false;

q.push(node->left);

q.push(node->right);

} else {

missing = true;

}

return true;

}

};

Python3

class Solution:

def isCompleteTree(self, root):

if not root: return True

q = collections.deque([root])

missing = False

while q:

size = len(q)

while size > 0:

size -= 1

node = q.popleft()

if node:

if missing: return False

q.append(node.left)

q.append(node.right)

else:

missing = True

return True

花花酱 LeetCode 111. Minimum Depth of Binary Tree

By zxi on December 15, 2018

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int minDepth(TreeNode* root) {

if (!root) return 0;

if (!root->left && !root->right) return 1;

int l = root->left ? minDepth(root->left) : INT_MAX;

int r = root->right ? minDepth(root->right) : INT_MAX;

return min(l, r) + 1;

}

};

Python3

class Solution:

def minDepth(self, root):

if not root: return 0

if not root.left and not root.right: return 1

l = self.minDepth(root.left)

r = self.minDepth(root.right)

if not root.left: return 1 + r

if not root.right: return 1 + l

return 1 + min(l, r)

Problem

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

Solution: Recursion

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int maxDepth(TreeNode* root) {

if (!root) return 0;

int l = maxDepth(root->left);

int r = maxDepth(root->right);

return max(l, r) + 1;

}

};

Python3

# Author: Huahua, 80 ms

class Solution:

def maxDepth(self, root):

if not root: return 0

l = self.maxDepth(root.left)

r = self.maxDepth(root.right)

return max(l, r) + 1

花花酱 LeetCode 938. Range Sum of BST

By zxi on November 10, 2018

Problem

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:

The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.

Solution: In-order traversal

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int rangeSumBST(TreeNode* root, int L, int R) {

if (!root) return 0;

int sum = 0;

if (root->val >= L) sum += rangeSumBST(root->left, L, R);

if (root->val >= L && root->val <= R) sum += root->val;

if (root->val <= R) sum += rangeSumBST(root->right, L, R);

return sum;

}

};

花花酱 LeetCode 919. Complete Binary Tree Inserter

By zxi on October 6, 2018

Problem

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:

CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
CBTInserter.get_root() will return the head node of the tree.

Example 1:

Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]

Example 2:

Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]

Note:

The initial given tree is complete and contains between 1 and 1000 nodes.
CBTInserter.insert is called at most 10000 times per test case.
Every value of a given or inserted node is between 0 and 5000.

Solution 2: Deque

Using a deck to keep track of insertable nodes (potential parents) in order.

Time complexity: O(1) / O(n) first call

Space complexity: O(n)

C++

// Author: Huahua

class CBTInserter {

public:

CBTInserter(TreeNode* root): root_(root), d_({root}) {}

int insert(int v) {

while (!d_.empty()) {

TreeNode* r = d_.front();

if (r->left && r->right) {

d_.push_back(r->left);

d_.push_back(r->right);

d_.pop_front();

} else if (r->left) {

r->right = new TreeNode(v);

return r->val;

} else {

r->left = new TreeNode(v);

return r->val;

}

TreeNode* get_root() { return root_; }

private:

std::deque<TreeNode*> d_;

TreeNode* root_;

};

Posts published in “Tree”

花花酱 LeetCode 958. Check Completeness of a Binary Tree

Solution:

C++

Python3

花花酱 LeetCode 111. Minimum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problem

花花酱 LeetCode 104. Maximum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

花花酱 LeetCode 938. Range Sum of BST

Problem

Solution: In-order traversal

C++

花花酱 LeetCode 919. Complete Binary Tree Inserter

Problem

Solution 2: Deque

C++