SOLID - 5 Principles of Object Oriented Single Responsibility Principle : A type should only have one reason to change Separation of concerns - different types/packages handling different, independent tasks/problems Open-Closed Principle Types should be open for extension but closed for modification Liskov Substitution Principle You should be able to substitute an embedding type in place of its embedded part Interface Segregation Principle Don’t put too much into an interface; spilt into separate interfaces For instance: There is an Animal interface with Walk method and Swim method, and Monkdy and Fish belong to Animal interfacel.
108. Convert Sorted Array to Binary Search Tree Level : Easy 原題連結 :Click 題目 : Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Example : Note Example 1:
Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: [0,-10,5,null,-3,null,9] is also accepted:
669. Trim a Binary Search Tree Level : Medium 原題連結 :Click 題目 : Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.
450. Delete Node in a BST Level : Medium 原題連結 :Click 題目 : 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. Follow up: Can you solve it with time complexity O(height of tree)?
701. Insert into a Binary Search Tree Level : Medium 原題連結 :Click 題目 : You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion.
235. Lowest Common Ancestor of a Binary Search Tree Level : Easy 原題連結 :Click 題目 : Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).