[leetcode]第十八部分

110-Balanced Binary Tree

问题难度: ♣

问题描述

给定一个二叉树, 判断其是否是高度均衡的.

对于这个问题, 高度均衡的二叉树定义如下: 每个节点的子树深度差异不超过1.

示例1

给定下面的树: [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

返回true.

示例2

给定下面的子树: [1,2,2,3,3,null,null,4,4]:


1 / \ 2 2 / \ 3 3 / \ 4 4

返回 false.

解题思路

对于当前节点, 其为深度均衡二叉树的充要条件如下:

  • 左子树和右子树的深度相差不超过1
  • 左子树为深度均衡二叉树
  • 右子树为深度均衡二叉树

因此, 需要使用一个额外的函数来获取树的深度,然后递归调用即可.

代码

# 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 isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def getTreeDepth(root):
            if root is None:
                return 0
            left_depth = getTreeDepth(root.left)
            right_depth = getTreeDepth(root.right)
            depth = left_depth if left_depth > right_depth else right_depth
            return 1 + depth
        if root is None:
            return True
        else:
            left_depth = getTreeDepth(root.left)
            right_depth = getTreeDepth(root.right)
            dis = left_depth - right_depth
            return dis * dis <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

111-Minimum Depth of Binary Tree

问题难度: ♣

问题描述

给定一个二叉树, 找到其最小的深度.

最小的深度指的是根节点到最近的叶子节点的距离

注意: 叶子节点为没有孩子的节点.

示例

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

解题思路

进行层次遍历, 如果遇到节点没有左孩子节点和右孩子节点,则停止遍历, 直接返回;否则的话, 将当前节点加到下一层,继续遍历.

代码

# 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 minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        cur_nodes = [root]
        depth = 1
        while len(cur_nodes) > 0:
            next_nodes = list()
            for i in range(len(cur_nodes)):
                cur_node = cur_nodes[i]
                if cur_node.left is None and cur_node.right is None:
                    return depth
                elif cur_node.left is None:
                    next_nodes.append(cur_node.right)
                elif cur_node.right is None:
                    next_nodes.append(cur_node.left)
                else:
                    next_nodes.append(cur_node.left)
                    next_nodes.append(cur_node.right)
            cur_nodes = next_nodes
            depth += 1
        return depth

112-Path Sum

问题难度: ♣

问题描述

给定一个二叉树和一个数值, 判断这棵树是否有根节点到叶子节点的路径之和加起来等于给定的和.

注意: 叶子节点是没有孩子的节点.

示例

给定下面的二叉树和sum=22:

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回true, 因为存在一条从根节点到叶子节点的路径: 5->4->11->2, 和为22.

解题思路

判断是否存在一条路径的和等于给定sum, 就需要遍历所有路径, 直到遇到满足条件的路径或者遍历完为止.

针对当前节点:

  • 如果为None,直接返回false
  • 如果其既没有左孩子又没有右孩子, 那么判断当前的值与给定的值是否相等, 如果相等, 则返回true;否则返回false
  • 否则, 向左走或向右走, 只要有一个满足条件即可
# 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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root is None:
            return False
        if root.left is None and root.right is None:
            return root.val == sum
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

113-Path Sum II

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树和一个数值, 返回根节点到叶子节点的路径之和加起来等于给定的和的所有路径.

注意: 叶子节点是没有孩子的节点.

示例

给定下面的二叉树和sum=22:

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回

[
   [5,4,11,2],
   [5,8,4,5]
]

解题思路

这道题目和之前遍历所有路径的问题类似, 需要判断路径之和是否等于sum即可.

使用一个栈存储当前路径的节点, 如果已经遍历过该节点的右子树, 那么直接将该节点设置为None.
使用另一个列表来标识当前路径的值.

从根节点开始, 每次取队尾的元素:

  • 如果它为None则标识该节点的右子树已经被遍历, 将其pop出来,并且将该节点对应的值从当前路径中pop出来. 然后将当前队尾设置为None(标识已经取到其right了), 接着如果right不为None, 则将right写到队尾.
  • 如果它为叶子节点, 则判断当前路径和和是否等于sum, 如果等于,则将其加到返回的列表中;然后pop出来,并且将该节点对应的值从当前路径中pop出来. 然后将当前队尾设置为None(标识已经取到其right了), 接着如果right不为None, 则将right写到队尾

这样一直遍历,直到所有节点遍历完成为止.

代码

# 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 pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        def checkPath(node_list, target):
            sum  = 0
            for node in node_list:
                sum += node
            return sum == target
        root_stack = [root]
        total_path = []
        cur_path = []
        while len(root_stack) > 0:
            cur_node = root_stack[-1]
            if cur_node is None:
                root_stack = root_stack[:-1]
                if len(root_stack) > 0:
                    tmp = root_stack[-1]
                    if tmp is not None:
                        root_stack[-1] = None
                        if tmp.right is not None:
                            root_stack.append(tmp.right)
                cur_path = cur_path[:-1]
            else:
                cur_path.append(cur_node.val)
                if cur_node.left is None and cur_node.right is None:
                    is_valid = checkPath(cur_path, sum)
                    if is_valid:
                        total_path.append(cur_path)
                    cur_path = cur_path[:-1]
                    root_stack = root_stack[:-1]
                    if len(root_stack) > 0:
                        tmp = root_stack[-1]
                        if tmp is not None:
                            root_stack[-1] = None
                            if tmp.right is not None:
                                root_stack.append(tmp.right)
                elif cur_node.left is not None:
                    root_stack.append(cur_node.left)
                else:
                    root_stack[-1] = None
                    root_stack.append(cur_node.right)
        return total_path

114-Flatten Binary Tree to Linked List

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树, 将其平滑成一个链表.例如, 给定下面的二叉树:


1 / \ 2 5 / \ \ 3 4 6

平滑后的链表如下所示:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解题思路

使用一个额外的队列来存储节点的右节点(假设为r_nodes). 从根节点开始:

对于当前节点:

  • 如果右节点不为None,则将其追加到队尾
  • 如果左节点不为None, 则将当前节点的右节点设置为左节点, 并将左节点设置为当前节点
  • 如果左节点为None:
    • 如果len(r_nodes)0, 那么直接返回
    • 否则, 将r_nodes[-1]设置为当前节点的右节点,,并且将右节点设置为当前节点, r_nodes = r_nodes[:-1]

代码

# 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 flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        cur_node = root
        right_nodes = []
        while cur_node is not None:
            #print cur_node.val, len(right_nodes)
            if cur_node.right is not None:
                right_nodes.append(cur_node.right)
            if cur_node.left is not None:
                cur_node.right = cur_node.left
            else:
                if len(right_nodes) > 0:
                    cur_node.right = right_nodes[-1]
                    right_nodes = right_nodes[:-1]
            cur_node.left = None
            cur_node = cur_node.right

115- Distinct Subsequences

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定一个字符串S和另一个字符串T, 计算S中与T相等的子序列的数目。

一个字符串的子序列是一个在不打乱剩余字符相对位置的前提下,从原始字符串中删除一部分(或者不删除)字符而形成的新字符串(例如,ACEABCDE的子序列而AEC则不是。

示例1

Input: S = "rabbbit", T = "rabbit"
Output: 3
解释:

如下所示, 有3种方式可以从`S`中生成"rabbit".
(下划符号 ^ 表示选中的字符)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例2

Input: S = "babgbag", T = "bag"
Output: 5
解释:

如下所示, 有5种方式可以从`S`中生成"bag".
(下划符号 ^ 表示选中的字符)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^   ^^
babgbag
  ^  ^^
babgbag
   ^^^

解题思路

突然想到一句话,只要是和字符串相关的题目都可以考虑一下动态规划…嗯,这题可以使用动态规划进行求解。

数学化memo[i][j]表示S中前i个字符中包含T中的前j个字符的子序列数目

接下来是转移方程

  • 如果S[i] != T[j],那么memo[i][j] = memo[i-1][j]
  • 如果s[i] == T[j],那么memo[i][j] = memo[i-1][j] + memo[i-1][j-1]
  • 如果i>=0, j=0,那么memo[0][0] = 1
  • 如果i=0, j>0,那么memo[0][j] = 0

代码

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        m, n = len(s) + 1, len(t) + 1
        memo = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            memo[i][0] = 1
        for i in range(1,m):
            for j in range(1,n):
                if s[i-1] != t[j-1]:
                    memo[i][j] = memo[i-1][j]
                else:
                    memo[i][j] = memo[i-1][j] + memo[i-1][j-1]
        return memo[m-1][n-1]

116-Populating Next Right Pointers in Each Node

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树:

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

将节点的每一个next指针指向其右边的节点。如果没有下一个右边的节点,next指针应该被设置为NULL

初始地,所有的next指针被设置为NULL

注意:

  • 我们只能使用固定的额外空间。
  • 可以使用递归的方法,在这个问题中,隐式的栈空间不会被计算为额外的空间。
  • 可以假设它是一个完美的二叉树(也就是说:所有叶子节点都在一个层级,每个父节点都有两个叶子节点)

示例

给定下面的二叉树:

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

在调用函数之后,树应该成为:

    1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

解题思路

本题按照层次的方法进行遍历,使用cur_stack来存储当前层,使用next_stack来存储下一层,直到下一层中不再有节点为止,针对每一层,遍历该层的节点,将当前节点的right设置为列表中的下一个值即可。

问题就变成了怎么从当前层得到下一层:针对当前层的每一个节点,当节点的leftright节点添加到下一层即可。

代码

# Definition for binary tree with next pointer.
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return
        cur_stack = [root]
        while len(cur_stack) > 0:
            next_stack = []
            for i in range(len(cur_stack) - 1):
                cur_stack[i].next = cur_stack[i+1]
                if cur_stack[i].left is not None:
                    next_stack.append(cur_stack[i].left)
                    next_stack.append(cur_stack[i].right)
            cur_stack[-1].next = None
            if cur_stack[-1].left is not None:
                next_stack.append(cur_stack[-1].left)
                next_stack.append(cur_stack[-1].right)
            cur_stack = next_stack
s = Solution()
root = TreeLinkNode(1)
a = TreeLinkNode(2)
b = TreeLinkNode(3)
c = TreeLinkNode(4)
d = TreeLinkNode(5)
e = TreeLinkNode(6)
f = TreeLinkNode(7)

root.left = a
root.right = b
a.left = c
a.right = d
b.left = e
b.right = f

s.connect(root)

cur_stack = [root]
while len(cur_stack) > 0:
    next_stack = []
    for node in cur_stack:
        if node.left is not None:
            next_stack.append(node.left)
        if node.right is not None:
            next_stack.append(node.right)
    start = cur_stack[0]
    ans = ""
    while start is not None:
        ans += str(start.val) + " "
        start = start.next
    print(ans)
    cur_stack = next_stack
1 
2 3 
4 5 6 7 
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注