美文网首页
Leetcode【700、872、897、965、1022】

Leetcode【700、872、897、965、1022】

作者: 牛奶芝麻 | 来源:发表于2019-10-28 17:48 被阅读0次
    问题描述:【Tree】700. Search in a Binary Search Tree
    解题思路:

    这道题是给一棵二叉搜索树(BST),查找给定的结点。结点不存在返回 NULL。

    利用 BST 的特点,进行二分查找即可。

    Python3 实现:
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def searchBST(self, root: TreeNode, val: int) -> TreeNode:
            if not root:
                return None
            if root.val == val:
                return root
            elif root.val > val:
                return self.searchBST(root.left, val)
            elif root.val < val:
                return self.searchBST(root.right, val)
    

    问题描述:【Tree】872. Leaf-Similar Trees
    解题思路:

    这道题是给两棵树,判断它们的叶子序列(从左到右)是否相同。

    将两棵树的叶子序列保存在 list 中,判断二者是否相同即可。

    1、判断叶子的条件是 root.left == None and root.right == None,返回 [root.val];
    2、还要注意单子树的情况([1, 2] 或 [1, null, 2]),应该返回 [];

    Python3 实现:
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
            def leafSeq(root):  # 得到树的叶子序列
                if not root:  # 防止单子树(如 [1,2] 或者 [1,null,2])
                    return []
                if root.left == None and root.right == None:  # 叶子
                    return [root.val]
                return leafSeq(root.left) + leafSeq(root.right)
            
            return leafSeq(root1) == leafSeq(root2)
    

    问题描述:【Tree】897. Increasing Order Search Tree
    解题思路:

    这道题是给一棵二叉搜索树,将结点按照从小到大重新排列,构造一棵只有右结点的树。

    先前序遍历将每个结点保存在 list 中,再构造只有右结点的树。构造右结点的树时,除了根结点 node 外,还要有一个工作指针 cur,在遍历 list 的过程中,cur 每次往右子树走(cur = cur.right),最后返回 node 即可。

    Python3 实现:
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def increasingBST(self, root: TreeNode) -> TreeNode:
            
            def in_order(root):  # 中序遍历,保存结点
                if not root:
                    return []
                return in_order(root.left) + [TreeNode(root.val)] + in_order(root.right)
            
            nodelist = in_order(root)
            node = cur = nodelist[0]  # node:指向根结点,cur:往右子树走
            for i in range(1, len(nodelist)):
                cur.right = nodelist[i]
                cur = cur.right
            return node
    

    问题描述:【Tree】965. Univalued Binary Tree
    解题思路:

    这道题是给一棵二叉树,判断其是否是单值二叉树(所有结点值都相同)。

    1、先将根结点的值作为目标值 tar,将 tar 也参与递归函数;
    2、如果 root 为 None,返回 True;
    3、如果 root.val == tar,就递归左右子树,返回左右子树的判断结果;
    4、否则返回 False。

    Python3 实现:
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def isUnivalTree(self, root: TreeNode) -> bool:
            if not root:
                return True
            self.tar = root.val  # 目标值
            return self.judge(root)
        
        def judge(self, root):
            if root == None:
                return True
            if root.val == self.tar:
                return self.judge(root.left) and self.judge(root.right)
            return False
    

    问题描述:【DFS、Tree】1022. Sum of Root To Leaf Binary Numbers
    解题思路:

    这道题是给一个 01 二叉树,计算从根到叶子所有二进制路径表示的十进制数字的总和。

    方法1(回溯法):

    第一种容易想到的方法就是 DFS 回溯法,对树进行深度优先搜索,将每条路径 path 保存在 paths 列表中,每次找到一条路径的出口是遇到叶子结点。最后,对 paths 进行遍历,将每条路径 path 中的二进制转化为十进制数进行累加(如 int("0101", 2) = 5)。这样做的空间复杂度为 O(n)。

    Python3 实现:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def sumRootToLeaf(self, root: TreeNode) -> int:
            def findPath(root, path):
                if not root:
                    return
                path += str(root.val)  # 往当前路径中添加当前结点
                if root.left == None and root.right == None:  # 到叶子结点,增加一条路径
                    paths.append(path)
                    return
                findPath(root.left, path)
                findPath(root.right, path)
            
            paths, sum = [], 0  # paths 保存每条路径
            findPath(root, "")
            for path in paths:
                sum += int(path, 2)   # 二进制转十进制
            return sum
    

    方法2(不使用额外空间的做法):

    有没有不使用额外空间的做法呢?当然有。可以使用前缀和 presum。

    在深度优先搜索的过程中,每增加一层,就修改当前路径的累加值,即 presum = presum * 2 + root.val如 1->0->1 (5)再碰到 1 就会执行 presum = presum * 2 + 1 = 11,刚好是 1->0->1->1(11)。

    具体做法如下:
    1、如果 root 为空,返回 0;
    2、更新前缀累加和 presum = presum * 2 + 1
    2、如果 root.left 或者 root.right 不为空,就递归求解左右子树路径和 return pathSum(root.left, presum) + pathSum(root.right, presum)
    3、最后返回 presum 就是答案;

    Python3 实现:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def sumRootToLeaf(self, root: TreeNode) -> int:
            def pathSum(root, presum):
                if not root:
                    return 0
                presum = presum * 2 + root.val  # 每增加一层修改当前路径累加值
                if root.left or root.right:  # 左右子树路径之和
                    return pathSum(root.left, presum) + pathSum(root.right, presum)
                return presum  # 到叶子结点
            
            return pathSum(root, 0)
    

    相关文章

      网友评论

          本文标题:Leetcode【700、872、897、965、1022】

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