码疯窝

LeetCode 每日一题 — Validate Binary Search Tree

2014/12/11 12:04:37    分类: 日志连载    0人评论 次浏览

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.

算法分析: 这道题目很似看简单, 但是曲解了题意, 花费了我不少功夫.
拿题一看, 很简单嘛, 拿节点值比较, 比左节点大, 比右节点小就OK, 于是直接可以写出来
return (root.left.val < root.val && root.right.val > root.val) ? isValidBST(root.left) && isValidBST(root.right) : false;
显示输入:

    10
    / \
   5   15
       / \
      6   20

未通过.

看了好久没发现问题, 每个节点都是比下一级的左节点大, 右节点小. 花了好久终于明白, 原来不能看单个节点, 要看整棵树.
此树中, 6属于10的右边节点, 却比10小, 故而错了. 正确的形式应该如此.

      3
    /  \
   1     5
  / \   / \
 0   2 4   6

理解好了题目意思就可以分析算法了.

if 是左节点
    将它分向右的那个节点->val < val < 父节点->val     // 如4为左节点, 父为5, 3将4分向右, 帮有  3 < 4 < 5
if 是右节点
    父节点->val < val < 将它分向左的那个节点->val       // 如2为右节点, 父为1, 3将2分向左, 帮有 1 < 2 < 3

如果无将比分向另一边的节点, 如0, 6, 那么对应的就是正无穷和负无穷. 当然在程序里面要考虑数据类型的取值范围.

算法明了, 接下来就是程序实现, 因为算法写得很清楚明了, 程序就写得草率点, 个人比较喜欢用三元, 不喜误喷.
其中要提的是因为在C++中, 可能是因为编译器的关系, int 和 long 型都是32位. 故无法使用long 去判断 int 的最大与最小, 故而我改为了 double 型, 但是java 和 python 中可以通过.

Java:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode node, long min, long max) {
        return (node == null) ? 
                true :
                (node.val < max && node.val >min) ?
                    this.isValidBST(node.left, min, node.val) && this.isValidBST(node.right, node.val, max) :
                    false;
    }
    
    public boolean isValidBST(TreeNode root) {
        return (root == null) ? true :
            this.isValidBST(root.left, (long)Integer.MIN_VALUE - 1, root.val) && 
            this.isValidBST(root.right, root.val, (long)Integer.MAX_VALUE + 1);
    }
}

C++:

    /** 
     * Definition for binary tree 
     * struct TreeNode { 
     *     int val; 
     *     TreeNode *left; 
     *     TreeNode *right; 
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
     * }; 
     */  
    class Solution {  
    public:
        bool isValidBST(TreeNode *node, double min, double max) {
            return (node == NULL) ?
                    true :
                    (node->val > min && node->val < max) ?
                        isValidBST(node->left, min, node->val) && isValidBST(node->right, node->val, max) :
                        false;
        }
    
        bool isValidBST(TreeNode *root) {
            return (root == NULL) ? true :
                    isValidBST(root->left, (double)INT_MIN - 1, root->val) && isValidBST(root->right, root->val, (double)INT_MAX + 1);
        }
    };

Python:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def valid(self, node, lmin, lmax):
        return (node == None) and True or ((node.val < lmax and node.val > lmin) and (self.valid(node.left, lmin, node.val) and self.valid(node.right, node.val, lmax)) or False)
         
    # @param root, a tree node
    # @return a boolean       
    def isValidBST(self, root):
        return (root == None) and True or (self.valid(root.left, -2147483649, root.val) and self.valid(root.right, root.val, 2147483648))
        
继续查看有关 日志连载的文章

0个访客评论