Press "Enter" to skip to content

Posts tagged as “tree”

花花酱 LeetCode 1382. Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

Constraints:

  • The number of nodes in the tree is between 1 and 10^4.
  • The tree nodes will have distinct values between 1 and 10^5.

Solution: Inorder + recursion

Use inorder traversal to collect a sorted array from BST. And then build a balanced BST from this sorted array in O(n) time.

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • The values of the nodes of the tree are unique.
  • target node is a node from the original tree and is not null.

Solution: Recursion

Traverse both trees in the same order, if original == target, return cloned.

Time complexity: O(n)
Space complexity: O(h)

C++

Python3

花花酱 LeetCode 1367. Linked List in Binary Tree

Given a binary tree root and a linked list with head as the first node. 

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.  

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

  • 1 <= node.val <= 100 for each node in the linked list and binary tree.
  • The given linked list will contain between 1 and 100 nodes.
  • The given binary tree will contain between 1 and 2500 nodes.

Solution: Recursion

We need two recursion functions: isSubPath / isPath, the later one does a strict match.

Time complexity: O(|L| * |T|)
Space complexity: O(|T|)

C++

花花酱 LeetCode 1361. Validate Binary Tree Nodes

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Example 4:

Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false

Constraints:

  • 1 <= n <= 10^4
  • leftChild.length == rightChild.length == n
  • -1 <= leftChild[i], rightChild[i] <= n - 1

Solution: Count in-degrees for each node

in degree must <= 1 and there must be exact one node that has 0 in-degree.

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution: Recursion

Recursively build a BST for a given range.

def build(nums, l, r):
if l > r: return None
m = l + (r – l) / 2
root = TreeNode(nums[m])
root.left = build(nums, l, m – 1)
root.right = build(nums, m + 1, r)
return root

return build(nums, 0, len(nums) – 1)

Time complexity: O(n)
Space complexity: O(logn)

C++

Java

Python3

JavaScript