美文网首页
[每日一题]98. Validate Binary Search

[每日一题]98. Validate Binary Search

作者: 何学诚 | 来源:发表于2019-04-13 19:36 被阅读0次
    1.树是真的麻烦啊!

    我认为,树是链表的一种“变形”,从单链表的一个指针,变成了二叉树的左右两根指针。
    它一衍生就成了图,然后还能应用在堆上,真的博大精深。
    但就是太难了。

    首先,常规操作:我先自己实现了下树。
    https://github.com/Wind0ranger/LeetcodeLearn/blob/master/5-tree/Tree.py
    简单说一下:

    1. 构建树的时候:这里的树,我是由字典保存的。然后通过两次循环构建成树的。第一层循环是为了建立节点,第二层循环是为了链接左右节点。
        @classmethod
        def build_from(cls, node_list):
            """通过节点信息构造二叉树
            第一次遍历我们构造 node 节点
            第二次遍历我们给 root 和 孩子赋值
            :param node_list: {'data': 'A', 'left': None, 'right': None, 'is_root': False}
            """
            node_dict = {}
            for node_data in node_list:
                data = node_data['data']
                node_dict[data] = BinTreeNode(data)
            for node_data in node_list:
                data = node_data['data']
                node = node_dict[data]
                if node_data['is_root']:
                    root = node
                node.left = node_dict.get(node_data['left'])
                node.right = node_dict.get(node_data['right'])
            return cls(root)
    

    2.遍历就是用递归的方法,真的很难想。

     # 先序遍历
        def preorder_trav(self, subtree):
            if subtree is not None:
                print(subtree.data)    # 递归函数里先处理根
                self.preorder_trav(subtree.left)   # 递归处理左子树
                self.preorder_trav(subtree.right)    # 递归处理右子树
    
        # 中序遍历
        def middle_trav(self, subtree):
            if subtree is not None:
                self.middle_trav(subtree.left)   # 递归处理左子树
                print(subtree.data)
                self.middle_trav(subtree.right)    # 递归处理右子树
    
        # 后序遍历
        def after_trav(self, subtree):
            if subtree is not None:
                self.after_trav(subtree.left)   # 递归处理左子树
                self.after_trav(subtree.right)    # 递归处理右子树
                print(subtree.data)
    

    层序用的是队列LILO,先加进来的先出去。

        # 层序遍历,使用队列思想不断往里面加入,不断出去.
        def layer_trav_use_queue(self, subtree):
            q = []
            q.append(subtree)
            while len(q) != 0:
                cur_node = q.pop(0)
                print(cur_node.data)
                if cur_node.left:
                    q.append(cur_node.left)
                if cur_node.right:
                    q.append(cur_node.right)
    

    再说这题目,链接:
    https://leetcode.com/problems/validate-binary-search-tree/

    98-validate-binary-search-tree.png

    这题,我想的很简单,直接中序遍历,查看是否是顺序排序。写的很差,我会修改的。今天太累了,不改了。

    2.题解:
    class Solution(object):
    
        def isValidBST(self, root):
            L1 = self.trav(root)
            return L1 == sorted(set(L1))
    
        # 中序遍历
        def trav(self, root):
            if root is None:
                return []
            return self.trav(root.left) + [root.val] + self.trav(root.right)
    
    3.完整代码

    查看链接:
    https://github.com/Wind0ranger/LeetcodeLearn/blob/master/5-tree/98-validate-binary-search-tree.py

    相关文章

      网友评论

          本文标题:[每日一题]98. Validate Binary Search

          本文链接:https://www.haomeiwen.com/subject/nkmlwqtx.html