Reproduced in public hook Java universe: mp.weixin.qq.com/s/bS8yCvHhD…

Author: Druid

What is the interviewer going to bury in your face about binary trees? Now let’s look at a topic to check your level.

Binary search trees have the following characteristics:

• The value of the root is greater than the value of all the left subtrees
• The value of the root is less than the value of all the right subtrees
• The left and right subtrees must also meet the above characteristics

Now given a binary tree, determine whether it is a binary search tree.

By definition, a binary search tree is essentially a pre-order traversal. Therefore, we can use the idea of sequential traversal to solve this problem.

First we simulate on this tree, using INT64_MIN for negative infinity and INT64_MAX for positive infinity.

1. Let’s assume that the root is always correct. If it is always true, then we can think of the node’s value as always: within the interval (INT64_MIN, INT64_MAX). Since the value of the binary tree is int, if you use int64 you can always be in the range.

2. By the definition of binary search trees, the left subtree is always smaller than the root 5, so the range of the left subtree should be set to (INT64_MIN, 5).

3. Given the duration of the binary search tree, the right subtree is always larger than the root 5, so the range of the right subtree should be set to (5, INT64_MAX).

4. And then if WE look at the left subtree of node 7, the range is going to be (5, 7).

After running the simulation, we can summarize the following characteristics:

• From the original binary tree, we can actually construct a “shadow” interval binary tree, but the node of the binary tree is an interval.

• The values in the old binary tree need to fall into the range of the new binary tree.

Therefore, the idea of solving the problem is:

How to effectively use the “interval” binary tree on the right to verify the validity of the binary tree on the left?

When the “interval” binary tree on the right cannot be constructed successfully, the original binary tree is an invalid binary search tree.

Note: We are not really building a “shadow” binary tree, we are doing this for ease of thought.

The shadow binary tree is generated from the original binary tree. Nodes in the tree are constantly splitting intervals, such as:

(INT64_MIN, INT64_MAX) -> (INT64_MIN, 5) , (5, INT64_MAX)

(5, INT64_MAX) -> (5, 7), (7, INT64_MAX)

We use the binary tree’s preorder traversal to traverse both binary trees simultaneously.

Note that the “shadow” binary tree is dynamically generated and we do not save its data structure.

For binomial tree boundaries, we need to consider one case:

An empty binary tree is defined as “less than” and “greater than”. If any position does not meet the definition of binary tree, you do not need to go through it again. Therefore, we should pay attention to fast return.

With that in mind, you can write the following core code.

``class Solution { private boolean ans = true; private void preOrder(TreeNode root, Long l, Long r) { // 1. If the empty tree / / 2. If you have nodes don't meet the requirements of BST if (root = = null | |! ans) { return; } // check if the current node is in the shadow of the binary tree. (l < root.val && root.val < r)) { ans = false; return; } preOrder(root.left, l, long.valueof (root.val)); PreOrder (root.right, long.valueof (root.val), r); } public boolean isValidBST(TreeNode root) { ans = true; preOrder(root, Long.MIN_VALUE, Long.MAX_VALUE); return ans; }}Copy the code``

We extend the traditional empirical pre-traversal by creating a “shadow” binary tree.

So the question is: find the hidden “shadow” binary tree.

In addition, when traversing a binary tree, if recursion is possible, it should also be possible to traverse a stack, or Morris.

Reproduced in public hook Java universe: mp.weixin.qq.com/s/bS8yCvHhD…

Author: Druid