LeetCode Day 20 (Day19 is rest day) binary tree (6/9)

It is not very easy, but it is important to understand how to think when you use recursion, and not to get sidetracked.

Question 1

654. Maximum Binary Tree

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Whenever we solve questions about constructing a binary tree , we can use a preorder traversal (middle → left → right). The root node is constructed first, and then the left and right subtrees are constructed.

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:
            return TreeNode(nums[0])
        node = TreeNode(0)
        maxValue = 0
        maxValueIndex = 0
        for i in range(len(nums)):
            if nums[i] > maxValue:
                maxValue = nums[i]
                maxValueIndex = i
        node.val = maxValue
        # left
        if maxValueIndex > 0:
            new_list = nums[:maxValueIndex]
            node.left = self.constructMaximumBinaryTree(new_list)
        # Right
        if maxValueIndex < len(nums) - 1:
            new_list = nums[maxValueIndex+1:]
            node.right = self.constructMaximumBinaryTree(new_list)
        return node

Question 2

617. Merge Two Binary Trees

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

It’s a bit fantastic that two binary trees need to be traversed at the same time.

This problem continues with the recursive three-step process:

1. Determine the parameters and return value of the recursive function:
   1. Pass in the root node of the two binary trees and return the root node of the merged tree.
2. Determine the termination condition
   1. If one of the two trees is null, return the other tree
3. Determine the logic of single level recursion
   1. Merge left subtree with left subtree, right subtree with right subtree

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1: 
            return root2
        if not root2: 
            return root1
        root1.val += root2.val # 中
        root1.left = self.mergeTrees(root1.left, root2.left) # Left
        root1.right = self.mergeTrees(root1.right, root2.right) # right
        
        return root1 

Question 3

700. Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Still applying the three steps of recursion and solving the problem in a recursive way

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if  not root or root.val == val:
            return root
 
        if root.val > val:
            return self.searchBST(root.left,val)
 
        if root.val < val:
            return self.searchBST(root.right,val)

Question 4

98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

In a medium-order traversal, the values of the output binary search tree nodes are ordered sequences.

With this property, verifying a binary search tree becomes equivalent to determining whether a sequence is incremental or not.

class Solution:
    def __init__(self):
        self.vec = []
 
    def traversal(self, root):
        if root is None:
            return
        self.traversal(root.left)
        self.vec.append(root.val)  # Transfer to array
        self.traversal(root.right)
 
    def isValidBST(self, root):
        self.vec = []  
        self.traversal(root)
        for i in range(1, len(self.vec)):
      
            if self.vec[i] <= self.vec[i - 1]:
                return False
        return True