Leetcode--Tree(python)

12296 ワード

98. Validate Binary Search Tree
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.
    

    treeの定義:val、left、right二叉検索ツリーは、各ノードの値が左ノードより大きく、右ノードより小さく、左ノードと右ノードもこの条件を満たすことを意味します.注意各ノードの判断については、最小値と最大値が与えられる.中間ノードは左側のすべてのサブノードより大きく、右側のすべてのサブノードより小さくなければならない(注意が小さく、等しくない).float(‘inf’)で最値を定義するので、再帰的には2つの値が入力される.
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def isValidBST(self, root, lowest = float('-inf'), highest = float('inf')):
            """
            :type root: TreeNode
            :rtype: bool
            """
            
            if root == None:
                return True
            
            val = root.val
            if val <= lowest or val>= highest:
                return False
            
            if not self.isValidBST(root.left, lowest, val):
                return False
            
            if not self.isValidBST(root.right, val, highest):
                return False
            
            return True
            
    

    第2の解法:中序遍歴を使用して、基本的にすべての二叉検索ツリーの操作はこのようにすることができます4つの主要な遍歴思想は:前序遍歴:ルートノード->左サブツリー->右サブツリー中序遍歴:左サブツリー->ルートノード->右サブツリー後序遍歴:左サブツリー->右サブツリー->ルートノード階層遍歴:階層遍歴だけでいい
    注意:preノードはclass内で定義され、定義時にselfはありません.
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        pre=None 
       
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if root is None: 
                return True
            Bool= self.isValidBST(root.left)
            
            if self.pre!=None:
                Bool=Bool and (self.pre.val<root.val)
            
            self.pre=root
            
            Bool=Bool and self.isValidBST(root.right)
            return Bool
            
    

    99. Recover Binary Search Tree
    Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.
    Example 1:
    
    Input: [1,3,null,null,2]
    
       1
      /
     3
      \
       2
    
    Output: [3,1,null,null,2]
    
       3
      /
     1
      \
       2
    Example 2:
    
    Input: [3,1,4,null,null,2]
    
      3
     / \
    1   4
       /
      2
    
    Output: [2,1,4,null,null,3]
    
      2
     / \
    1   4
       /
      3
    

    Follow up:
    A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
    同様に中順ループを使用すればよいので、preノードが前駆ノードを表すことを定義する必要があります.2つのノードが逆転しているので、2つのノードの位置を見つけるだけです.n 1で1番目のずれの要素を格納し、n 2で2番目を格納し、交換すればよい.
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def recoverTree(self, root):
            """
            :type root: TreeNode
            :rtype: None Do not return anything, modify root in-place instead.
            """
            self.n1, self.n2, self.pre = None, None, None
            self.inorder(root)
            self.n1.val, self.n2.val = self.n2.val, self.n1.val
            
            
        def inorder(self, root):
            if root ==None:
                return
            self.inorder(root.left)
            if self.pre!=None and self.pre.val > root.val:
                if self.n1 == None:
                    self.n1=self.pre
                self.n2=root
                
            self.pre=root
            self.inorder(root.right)