Press "Enter" to skip to content

Posts tagged as “binary tree”

花花酱 LeetCode 337. House Robber III

题目大意:给你一棵二叉树,不能同时取两个相邻的节点(parent/child),问最多能取得的节点的值的和是多少。

Problem:

https://leetcode.com/problems/house-robber-iii/description/

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Idea: 

Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)

Solution 1: Recursion w/o memorization 

Time complexity: O(n^2)

Space complexity: O(n)

C++

Solution 2: Recursion w/ memorization 

Time complexity: O(n)

Space complexity: O(n)

Solution 3: Recursion return children’s value

Python3

Related Problems:

 

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

Solution 2:

Solution 3:

 

花花酱 LeetCode 637. Average of Levels in Binary Tree

 

Problem:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

 

Time Complexity:

O(n)

Space Complexity:

O(h)

Solution 1:

BFS

Solution 2:

DFS

 

Related Problems:

花花酱 LeetCode 654. Maximum Binary Tree

 

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Idea:

Recursion

Solution:

With copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(nlogn) ~ O(n^2)

running time 79ms

Without copy

Time complexity: O(nlogn) ~ O(n^2)

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

running time 66ms

 

花花酱 LeetCode 669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Example 2:

This problem can be solved with recursion

There 3 cases in total depends on the root value and L, R

Time complexity: O(n)

Space complexity: O(1)

Solution:

The previous solution has potential memory leak for languages without garbage collection.

Here’s the full program to delete trimmed nodes.

Example output