leetcode-297. 二叉树的序列化与反序列化

|
| 1.9k | 2 分钟

leetcode-297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例: 

1
2
3
4
5
6
7
8
你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5
序列化为 "[1,2,3,null,null,4,5]"

思路： 用了简单的先序递归思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        ans = []
        self.traverse(root, ans)
        output = ''.join(ans)
        return output
    
    def traverse(self, root, ans):
        if not root:
            ans.append('null')
            ans.append(',')
            return
        
        ans.append(str(root.val))
        ans.append(',')
        
        self.traverse(root.left, ans)
        self.traverse(root.right, ans)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        anslist = data.split(',')
        return self.traversed(anslist)
        
    def traversed(self, anslist):
        if not anslist:
            return None
        first = anslist[0]
        del anslist[0]
        if first == 'null':
            return None
        root = TreeNode(int(first))
        
        root.left = self.traversed(anslist)
        root.right = self.traversed(anslist)
        
        return root

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

leetcode-652 寻找重复的子树

|
| 1.2k | 1 分钟

leetcode-652 寻找重复的子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1:

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

下面是两个重复的子树：

1
2
3
  2
 /
4

和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    4
```    
因此，你需要以列表的形式返回上述重复子树的根结点。

思路：
1. 先了解子树结构，通过左子树和右子树遍历了解的以x为根节点的子树形式
2. 通过备忘录保存已出现的子树形式，来判断是否重复

```python3
import collections
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.memo = collections.defaultdict(int)
        self.res = []
    
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        self.traverse(root)
        return self.res
    
    def traverse(self, root):
        if not root:
            return '#'
        
        left = str(self.traverse(root.left))
        right = str(self.traverse(root.right))
        
        subtree = left + ',' + right + ',' + str(root.val)
        
        freq = self.memo[subtree]
        if freq == 1:
            self.res.append(root)
        self.memo[subtree] +=1
        return subtree

leetcode-106 从中序与后序遍历序列构造二叉树

|
| 1.3k | 1 分钟

leetcode-106 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

1
2
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树： 

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

思路：

和之前题目的思路类似，通过后续遍历的最后一个元素可以确定根节点，通过后序遍历的根节点找到中序遍历中根节点的位置，确定左右子树，递归处理即刻。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        root = self.build(inorder, 0, len(inorder)-1, postorder, 0, len(postorder)-1)
        return root
        sz
    def build(self, inorder, instart, inend, postorder, poststart, postend):
        if poststart > postend:
            return
        rootVal = postorder[postend]
        index = 0
        for i in range(instart, inend+1):
            if inorder[i] == rootVal:
                index = i
                break
        root = TreeNode(rootVal)
        leftsize = index - instart
        root.left = self.build(inorder, instart, index-1, postorder, poststart, poststart+leftsize-1)
        root.right = self.build(inorder, index + 1, inend, postorder, poststart+leftsize, postend-1)
        return root

leetcode-105 从前序与中序遍历序列构造二叉树

|
| 1.3k | 1 分钟

leetcode-105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树： 

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

思路：

前序遍历中，第一个是根节点后面是左子树与右子树，中序遍历是左子树根节点和右子树，通过前序遍历找到中序遍历中的根节点，然后对应递归处理左子树和右子树即刻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        root = self.build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
        return root
        
        
    def build(self, preorder, prestart, preend, inorder, instart, inend):
        if prestart > preend:
            return
        rootval = preorder[prestart]
        index = 0
        for i in range(instart, inend+1):
            if inorder[i] == rootval:
                index = i
                break
        root = TreeNode(rootval)
        leftsize = index - instart
        root.left = self.build(preorder,prestart+1, prestart+leftsize ,inorder, instart, index-1)
        root.right = self.build(preorder,prestart+leftsize+1,preend ,inorder, index+1, inend)
        
        return root

leetcode-654 最大二叉树

|
| 946 | 1 分钟

654. 最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ： 

1
2
3
4
5
6
7
8
9
10
输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

思路是先找到数组中最大的值，然后左右部分循环递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if len(nums)<= 0:
            return
        max_num = max(nums)
        root = TreeNode(max_num)
        left_nums = nums[:nums.index(max_num)]
        right_nums = nums[nums.index(max_num)+1:]
        left = self.constructMaximumBinaryTree(left_nums)
        right = self.constructMaximumBinaryTree(right_nums)
        root.left = left
        root.right = right
        return root

leetcode-116 填充每个节点的下一个右侧节点指针

|
| 1.1k | 1 分钟

leetcode-116 填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

实现递归方法将两个左右子树进行相连，递归即刻。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        self.connectwithtwonodes(root.left, root.right)
        return root
        
    def connectwithtwonodes(self, left, right):
        if not left or not right:
            return
        left.next = right
        self.connectwithtwonodes(left.left, left.right)
        self.connectwithtwonodes(right.left, right.right)
        self.connectwithtwonodes(left.right, right.left)

leetcode-114 二叉树展开为链表

|
| 1k | 1 分钟

leetcode-114 二叉树展开为链表

给定一个二叉树，原地将它展开为一个单链表。

 

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

思路： 对子树进行递归展开，当左右子树都展开完了以后，将左子树接到右子树，再将原来的右子树接上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        if root is None:
            return 
        
        # 左右子树展开
        self.flatten(root.left)
        self.flatten(root.right)
        

        left = root.left
        right = root.right

        # 将左子树接到根右侧节点
        root.right = left
        root.left = None
        
        # 将原来的右子树接到现在右子树的末尾
        p = root
        while p.right:
            p = p.right
        p.right = right

leetcode-226 翻转二叉树

|
| 607 | 1 分钟

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

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

输出：

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

思路： 用先序递归遍历每个节点，对每个节点的左右子节点进行交换，然后递归左树和右树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

【西瓜书】阅读笔记 1. 绪论

|
| 1.2k | 1 分钟

绪论

引言

机器学习：假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过经验E在T中任务上获得了性能改善，则我们就说关于T和P，该程序对E进行了学习。

阅读全文 »