Press "Enter" to skip to content

Posts published in “Tree”

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

By zxi on March 5, 2018

题目大意：给你一棵树，返回每一层最大的元素的值。

You need to find the largest value in each row of a binary tree.

Example:

Solution 1: Inorder traversal + depth info

C++

Python3

 

花花酱 LeetCode 513. Find Bottom Left Tree Value

By zxi on March 5, 2018

题目大意：给你一棵树，返回左下角（最后一行最左面）的节点的值。

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Example 2: 

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution 1: Inorder traversal with depth info

The first node visited in the deepest row is the answer.

Python3

 

 

花花酱 LeetCode 508. Most Frequent Subtree Sum

By zxi on March 2, 2018

 

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

 

Python

 

花花酱 LeetCode 783. Minimum Distance Between BST Nodes

By zxi on February 10, 2018

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Note:

  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node’s value is an integer, and each node’s value is different.

Solution 1: In order traversal 

Time complexity: O(n)

Space complexity: O(n)

C++

Related Problems:

花花酱 LeetCode 652. Find Duplicate Subtrees

By zxi on December 31, 2017

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

2
/
4

and

4

Therefore, you need to return above trees’ root in the form of a list.

Solution 1: Serialization

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

C++

Solution 2: int id for each unique subtree

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

C++