Posts published in “Tree”

花花酱 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_;

};

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

By zxi on September 14, 2018

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the binary tree.

Solution 1: Recursion

Time complexity: O(n)

Space complexity: O(h)

For a given root, recursively call LCA(root.left, p, q) and LCA(root.right, p, q)

if both returns a valid node which means p, q are in different subtrees, then root will be their LCA.

if only one valid node returns, which means p, q are in the same subtree, return that valid node as their LCA.

C++

// Author: Huahua

class Solution {

public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (!root || root == p || root == q) return root;

TreeNode* l = lowestCommonAncestor(root->left, p, q);

TreeNode* r = lowestCommonAncestor(root->right, p, q);

if (l && r) return root;

return l ? l : r;

}

};

Java

// Author: Huahua

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root == p || root == q) return root;

TreeNode l = lowestCommonAncestor(root.left, p, q);

TreeNode r = lowestCommonAncestor(root.right, p, q);

if (l == null || r == null) return l == null ? r : l;

return root;

}

Python3

# Author: Huahua

class Solution:

def lowestCommonAncestor(self, root, p, q):

if any((not root, root == p, root == q)): return root

l = self.lowestCommonAncestor(root.left, p, q)

r = self.lowestCommonAncestor(root.right, p, q)

if not l or not r: return l if l else r

return root

Posts published in “Tree”

花花酱 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++

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

Problem

Solution 1: Recursion

C++

Java

Python3

Related Problems: