Algorithm - algoexpert | chenoiLab

icon

password

Reverse Polish Notation Min Height BST Sample Input Sample Output Solution Reconstruct BST Sample Input Sample Output Solution Find Successor Sample Input & Output Solution

Reverse Polish Notation

Oct 31, 2023

You're given a list of string tokens representing a mathematical expression using Reverse Polish Notation. Reverse Polish Notation is a notation where operators come after operands, instead of between them. For example 2 4 + would evaluate to 6. Parenthesis are always implicit in Reverse Polish Notation, meaning an expression is evaluated from left to right. All of the operators for this problem take two operands, which will always be the two values immediately preceding the operator. For example, 18 4 - 7 / would evaluate to ((18-4) / 7) or 2. Write a function that takes this list of tokens and returns the result. Your function should support four operators: + , - , * , and / for addition, subtraction, multiplication, and division respectively. Division should always be treated as integer division, rounding towards zero. For example, 3 / 2 evaluates to 1 and -3 / 2 evaluates to -1. You can assume the input will always be valid Reverse Polish Notation, and it will always result in a valid number. Your code should not edit this input list.

给定一个字符串列表 tokens，表示使用逆波兰表达式的数学表达式。逆波兰表达式是一种操作符在操作数之后而不是之间的表达式格式。例如，2 4 + 的计算结果为 6。逆波兰表达式中的括号始终是隐含的，意味着表达式从左到右进行计算。这个问题中的所有操作符都需要两个操作数，这两个操作数将始终位于操作符之前。例如，18 4 - 7 / 的计算结果为 ((18-4) / 7) 或 2。编写一个函数，接受这个 tokens 列表，并返回计算结果。你的函数应该支持四种操作符：+、-、* 和 /，分别表示加法、减法、乘法和除法。除法应该始终被视为整数除法，向零取整。例如，3 / 2 的计算结果为 1，-3 / 2 的计算结果为 -1。你可以假设输入始终是有效的逆波兰表达式，并且它将始终得到有效的数字。你的代码不应该修改这个输入列表。

Min Height BST

Oct 31, 2023

Write a function that takes in a non-empty sorted array of distinct integers, constructs a BST from the integers, and returns the root of the BST.

The function should minimize the height of the BST. You've been provided with a BST class that you'll have to use to construct the BST. Each BST node has an integer value, a left child node, and a right child node. A node is said to be a valid BST node if and only if it satisfies the BST property: its value is strictly greater than the values of every node to its left; its value is less than or equal to the values of every node to its right; and its children nodes are either valid BST nodes themselves or None / null .

A BST is valid if and only if all of its nodes are valid BST nodes. Note that the BST class already has an insert method which you can use if you want.

编写一个函数，它接受一个非空的已排序且不重复的整数数组，从这些整数构建一个二叉搜索树 (BST)，并返回 BST 的根节点。
该函数应该使得 BST 的高度最小化。你已经获得了一个 BST 类，你需要使用它来构建 BST。每个节点都有一个整数 value，一个左子节点和一个右子节点。只有满足 BST 属性的节点才被认为是有效的 BST 节点：它的比其左侧每个节点的值都严格大；它小于等于其右侧每个节点的值；它的子节点要么是有效的节点本身，要么是 None / null。
只有当所有节点都是有效的 BST 节点时，BST 才是有效的。请注意，BST 类已经有一个 insert 方法，你可以使用它（如果需要）。

Sample Input

array=[1,2,5,7,10,13,14,15,22]

Sample Output

Solution

保证左边和右边有差不多数量的nodes

所有left的nodes值小于root

但是如果数列中有多个重复值，root就不是中心数，因为也会导致skewnes

只要是distinct，那么中间数就算是偶数，随便取都能获得同样结果

Space = O(N), N is length of the array

TIme = O(NlogN), insert in a binary tree 需要 logN time

直接递归传值给BST，BST insert方法会自动把值放到最balanced的位置

但是也可以考虑这个O(N)方法：把insert方法替换为直接和array中点比较，并且把left或者right作为新的bst树进行递归

Reconstruct BST

The pre-order traversal of a Binary Tree is a traversal technique that starts at the tree's root node and visits nodes in the following order:

Current node

Left subtree

Right subtree

Given a non-empty array of integers representing the pre-order traversal of a Binary Search Tree (BST), write a function that creates the relevant BST and returns its root node.

The input array will contain the values of BST nodes in the order in which these nodes would be visited with a preorder traversal.

Each BST node has an integer value, a left child node, and a right child node. A node is said to be a valid BST node if and only if it satisfies the BST property: its value is strictly greater than the values of every node to its left; its value is less than or equal to the values of every node to its right; and its children nodes are either valid BST nodes themselves or None / null.

二叉树的前序遍历是一种遍历技术，它从树的根节点开始，并按以下顺序访问节点：
当前节点
左子树
右子树
给定一个非空的整数数组，代表二叉搜索树（BST）的前序遍历，编写一个函数来创建相关的BST，并返回其根节点。
输入数组将包含BST节点的值，这些节点的顺序与前序遍历访问这些节点的顺序相同。
每个BST节点都有一个整数值，一个左子节点和一个右子节点。只有当节点满足BST属性时，该节点才被认为是有效的BST节点：其值严格大于其左边每个节点的值；其值小于或等于其右边每个节点的值；其子节点要么是有效的BST节点，要么是None / null。

Sample Input

Sample Output

Solution

前序遍历是一种树的遍历方法，它按照“根节点-左子树-右子树”的顺序访问节点。这意味着在遍历过程中，我们首先访问当前节点（根节点），然后遍历左子树，最后遍历右子树。

这是因为在 BST 中，左子树的节点总是小于根节点，右子树的节点总是大于根节点，而前序遍历先访问根节点，然后访问左子树，最后访问右子树。

数组遍历时，先找当前数右边最大的index，再找到这个index之间第一个遇到的小的

solution2

给每个节点都一个范围 - time O(N) Space O(h)

subList不要拼错

如果如果不加这个，就会一直sublist下去，就会报错

⚠️

java.lang.IllegalArgumentException: fromIndex(1) > toIndex(0)

Find Successor

Write a function that takes in a Binary Tree (where nodes have an additional pointer to their parent node) as well as a node contained in that tree and returns the given node's successor.

A node's successor is the next node to be visited (immediately after the given node) when traversing its tree using the in-order tree-traversal technique. A node has no successor if it's the last node to be visited in the in-order traversal.

If a node has no successor, your function should return None / null . Each BinaryTree node has an integer value, a parent node, a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null.

编写一个函数，该函数接收一个二叉树（其中节点有一个指向其父节点的额外指针）以及包含在该树中的一个节点，并返回给定节点的后继者。
节点的后继者是使用中序树遍历技术遍历其树时（紧接在给定节点之后）要访问的下一个节点。如果一个节点是中序遍历中最后一个被访问的节点，那么它没有后继者。
如果一个节点没有后继者，你的函数应该返回 None / null。每个BinaryTree节点都有一个整数value，一个parent节点，一个left子节点和一个right子节点。子节点可以是BinaryTree节点，也可以是None / null。

Sample Input & Output

Solution

前序遍历、中序遍历和后序遍历是二叉树的遍历方式。

前序遍历：首先访问根节点，然后是左子树，最后是右子树。
中序遍历：首先访问左子树，然后是根节点，最后是右子树。
后序遍历：首先访问左子树，然后是右子树，最后是根节点。
前序遍历的结果是：A → B → D → E → C → F
中序遍历的结果是：D → B → E → A → C → F
后序遍历的结果是：D → E → B → F → C → A

Solution1

储存in-order traversal的array，搜索这个array找到那个值
time O(n)
space O(n)

Solution2

📌

the node successor is going to be the furthest left node in the node’s right subtree 右子树存在就找右子树最左边的节点

📌

look up the tree, going up to all of the parents, get a point where we came from the left child of a parent 右子树不存在就往上找找到根

⚠️

找到一个node，那么一定会找它右边的node

一个node如果有左节点，这个左节点肯定不会是其successor

time O(h)

constant space

🔥

Conclusion

如果给定节点有右子树，那么在中序遍历中的下一个节点就是该右子树中最左边的节点。

如果给定节点没有右子树，我们需要向上遍历树，找父节点，如果当前点属于其左子树，就返回父节点。如果是在祖先节点的右子树，那就继续向上。

要用一个BinaryTree currentNode = node; 来找