Press "Enter" to skip to content

Posts tagged as “inorder”

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

  • Each tree has at most 5000 nodes.
  • Each node’s value is between [-10^5, 10^5].

Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

C++

C++/STL

花花酱 LeetCode 1273. Delete Tree Nodes

A tree rooted at node 0 is given as follows:

  • The number of nodes is nodes;
  • The value of the i-th node is value[i];
  • The parent of the i-th node is parent[i].

Remove every subtree whose sum of values of nodes is zero.

After doing so, return the number of nodes remaining in the tree.

Example 1:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

Constraints:

  • 1 <= nodes <= 10^4
  • -10^5 <= value[i] <= 10^5
  • parent.length == nodes
  • parent[0] == -1 which indicates that 0 is the root.

Solution: Inorder Traversal

For each node, return the sum of all its subtrees and number of nodes including itself after removal.

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

C++

花花酱 LeetCode 938. Range Sum of BST

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:

  1. The number of nodes in the tree is at most 10000.
  2. The final answer is guaranteed to be less than 2^31.

Solution: In-order traversal

Time complexity: O(n)

Space complexity: O(n)

C++

花花酱 LeetCode 897. Increasing Order Search Tree

Problem

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

Note:

  1. The number of nodes in the given tree will be between 1 and 100.
  2. Each node will have a unique integer value from 0 to 1000.

Solution: In-order traversal

root = 5
inorder(root.left) 之后
self.prev = 4
(1-4)已经处理完了,这时候的树是很奇怪的一个形状,3即是2的右子树,又是5的左子树。
   1
    \
     2    5
      \  /  \ 
       3     6
        \     \
 prev -> 4     8
             /  \
            7    9
—————————
5.left = None # 把5->3的链接断开
5
 \
  6
   \
    8
   /  \
  7    9
—————————–
self.prev.right = root  <=> 4.right = 5
把5接到4的右子树
1
 \
  2
   \
    3
     \
      4
       \
        5 <– prev
         \
          6
           \
            8
          /   \
         7     9
self.prev = root <=> prev = 5
inorder(5.right) <=> inorder(6) 然后再去递归处理6(及其子树)即可。

Time complexity: O(n)

Space complexity: O(n)

C++

Java

Python3

花花酱 LeetCode 538. Convert BST to Greater Tree

Problem

题目大意:把二叉搜索树的每个节点加上比他大的节点的和。

https://leetcode.com/problems/convert-bst-to-greater-tree/description/

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Solution: reversed inorder traversal

in a BST, we can visit every node in the decreasing order. Using a member sum to track the sum of all visited nodes.

Time complexity: O(n)

Space complexity: O(1)

C++