Press "Enter" to skip to content

Posts published in “Tree”

花花酱 LeetCode 331. Verify Preorder Serialization of a Binary Tree

Problem

题目大意:验证二叉树前序遍历的序列化是否合法。

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing nullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution: Recursion

  1. If a node is not null, it must has two children, thus verify left subtree and right subtree recursively.
  2. If a not is null, the current char must be ‘#’

Time complexity: O(n)

Space complexity: O(h)

C++

花花酱 LeetCode 814. Binary Tree Pruning

Problem:

题目大意:把不含有1的节点的子树全部删除。

https://leetcode.com/problems/binary-tree-pruning/description/

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.


Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]



Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]



Note:

  • The binary tree will have at most 100 nodes.
  • The value of each node will only be 0 or 1.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

Java

 

Python3

 

花花酱 LeetCode 450. Delete Node in a BST

Problem

https://leetcode.com/problems/delete-node-in-a-bst/description/

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Solution: Recursion

Time complexity: O(h)

Space complexity: O(h)

C++

v2

 

花花酱 LeetCode 437. Path Sum III

Problem

题目大意:给你一棵二叉树,返回单向的路径和等于sum的路径数量。

https://leetcode.com/problems/path-sum-iii/description/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution 1: Recursion

Time complexity: O(n^2)

Space complexity: O(n)

C++

Solution 2: Running Prefix Sum

Same idea to 花花酱 LeetCode 560. Subarray Sum Equals K

Time complexity: O(n)

Space complexity: O(h)

C++

Related Problem

 

花花酱 LeetCode 94. Binary Tree Inorder Traversal

Problem

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

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

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

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

Solution 2: Iterative