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....
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree Given two binary trees original and cloned and given a reference to a node target in the original tree. The cloned tree is a copy of the original tree. Return a reference to the same node in the cloned tree. Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree....
538. Convert BST to Greater Tree Given the root of 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. As a reminder, a binary search tree is a tree that satisfies these constraints: The left subtree of a node contains only nodes with keys less than the node’s key....
897. Increasing Order Search Tree Given the root of a binary search 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 one right child. 1 2 3 4 Example 1: Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 2 3 4 Example 2: Input: root = [5,1,7] Output: [1,null,5,null,7] Constraints:...
1387. Sort Integers by The Power Value The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps: if x is even then x = x / 2 if x is odd then x = 3 * x + 1 For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1)....
1814. Count Nice Pairs in an Array You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions: 0 <= i < j < nums.length nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) Return the number of nice pairs of indices....
872. Leaf-Similar Trees Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi. Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists. Notice that you can return the vertices in any order. 1 2 3 4 5 Example 1: Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3] Explanation: It's not possible to reach all the nodes from a single vertex....
563. Binary Tree Tilt Given the root of a binary tree, return the sum of every tree node’s tilt. The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if there the node does not have a right child....
235. Lowest Common Ancestor of a Binary Search Tree 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)....
114. Flatten Binary Tree to Linked List Given the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. 1 2 3 4 Example 1: Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6] 1 2 3 4 Example 2: Input: root = [] Output: [] 1 2 3 4 Example 3: Input: root = [0] Output: [0] Constraints:...
107. Binary Tree Level Order Traversal II Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root). 1 2 3 4 Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]] 1 2 3 4 Example 2: Input: root = [1] Output: [[1]] 1 2 3 4 Example 3: Input: root = [] Output: [] Constraints:...
102. Binary Tree Level Order Traversal Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level). 1 2 3 4 Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] 1 2 3 4 Example 2: Input: root = [1] Output: [[1]] 1 2 3 4 Example 3: Input: root = [] Output: [] Constraints: The number of nodes in the tree is in the range [0, 2000]....
105. Construct Binary Tree from Preorder and Inorder Traversal Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. 1 2 3 4 Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] 1 2 3 4 Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1] Constraints:...
145. Binary Tree Postorder Traversal Given the root of a binary tree, return the postorder traversal of its nodes’ values. 1 2 3 4 Example 1: Input: root = [1,null,2,3] Output: [3,2,1] 1 2 3 4 Example 2: Input: root = [] Output: [] 1 2 3 4 Example 3: Input: root = [1] Output: [1] 1 2 3 4 Example 4: Input: root = [1,2] Output: [2,1] 1 2 3 4 Example 5: Input: root = [1,null,2] Output: [2,1] Constraints:...
94. Binary Tree Inorder Traversal Given the root of a binary tree, return the inorder traversal of its nodes’ values. 1 2 3 4 Example 1: Input: root = [1,null,2,3] Output: [1,3,2] 1 2 3 4 Example 2: Input: root = [] Output: [] 1 2 3 4 Example 3: Input: root = [1] Output: [1] 1 2 3 4 Example 4: Input: root = [1,2] Output: [2,1] 1 2 3 4 Example 5: Input: root = [1,null,2] Output: [1,2] Constraints:...