F0a425865eb009348e6c563e76aeeba0
(难度Medium)Problem 98. Validate Binary Search Tree(判断二分查找树是否合法)

链接

Validate Binary Search Tree - LeetCode

难度等级

Medium

题干

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a 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.

题意

给定一个二分查找树,判断二分查找时是否合法。

一棵合法的二分查找树具有以下条件:

根节点左子树上的所有元素小于它,并且右子树上的所有元素大于它,且不允许出现相同的元素。

样例

Example 1:

    2
   / \
  1   3

**Input:** [2,1,3]
**Output:** true

Example 2:

    5
   / \
  1   4
     / \
    3   6

**Input:** [5,1,4,null,null,3,6]
**Output:** false
**Explanation:** The root node’s value is 5 but its right child’s value is 4.

题解

一开始我觉得这题很简单,我们只需要遍历这棵树,然后判断它的左右节点是否合法就完事了。

但是后来一想,想到了反例。我们直接递归的话,没办法获取到父亲再往上的节点的信息。是有可能构成冲突的,比方说当前节点的值是5,它的右孩子是7,我们目测来看是合法的。但如果说如果当前节点是父亲的左孩子,并且它的父亲是6的话,那么就是非法了。

也就是说我们在判断的时候,除了需要考虑自己的父亲之外,还需要考虑从根节点到当前一整个链路上的值的情况。

但是这还是比较复杂,我们怎么维护一整个链路上的值呢?如果每次都遍历的话,实在是太耗资源了。

top Created with Sketch.