程序员的玩具

LeetCode刷题笔记——Tree

662. Maximum Width of Binary Tree bangbang

一上来的思路就是层次遍历，一开始用的是deque，这样的话就要自己往里面加分隔符，确定宽度。还有就是遇到空节点也不能停，要接着向队列里面压入两个空节点，然后每一层结束时判断最左非空节点和最右非空节点之间的节点数。
然后超时了。。。看了一下调用栈，就是空节点太多了，然后转回溯法试了一下，还是没能解决空节点的问题。注意的是每一层最左非空节点的左边的节点都不用考虑，右边的同理，然后用了两个数组进行层次遍历，然后加了一些小trick，每层最左最右的空节点直接跳过，勉勉强强的AC了，代码最后也是很丑陋。
然后看了top1的代码。。。思路真的很巧妙。。一开始我也往这边想了，就是贴着两边找，但是不知道怎么确定位置。位置这点怎么能没想到呢，刚刷完堆的题，对于完全二叉树，每个节点的紧凑表示后的位置是确定的啊！那然后给每个节点一个编号，然后随意遍历这棵树，看同一层中的编号的差值就好了。
现在觉得棒棒，多刷刷可能就好了。树的核心思想就是那几个遍历，这道题其实没有脱离框架的。

637. Average of Levels in Binary Tree

做完662看到了669然后没有思路，然后觉得这道题好欺负就做这道题了。层次遍历，双数组，挺简单的。需要区分层次的时候感觉双数组加上一个指示变量这种方法挺好的，要是用一个队列的话需要处理层次的问题。用两个数组加上指示变量，每次换层次的时候的代价是指示变量变一下，current模拟指针改变指向，然后当前层数组clear一下，应该是常数级别的操作还不需要额外空间。
要是有更好的方法会更新这个方法的，目前来看就先用这个吧。

669. Trim a Binary Search Tree

昨天晚上困了看了这道题没思路，今天一早做这道题，仔细一琢磨倒是不难，就是递归。但是我用递归做完之后发现效率好低，琢磨有没有优化的方法。
捉摸了一下没想出来，看了top1的代码，思路没有大问题，又跑了一次，就打败100%了。。

226. Invert Binary Tree

典型题。

559. Maximum Depth of N-ary Tree

数据结构不能用leetcode自带的辅助函数初始化了，算法倒是不难。用backtrack，实际上是DFS，在对象里保存最大深度即可。

653. Two Sum IV

结合前面几种Two Sum问题，原始的问题在官方Solution中给了三种解法，可以两次遍历，可以使用HashTable加上Two Pass，更好的就是HashTable加上One Pass。另外一种问题的变形是有序的输入求解TwoSum问题，那可以用双指针来解决。这道题考虑能使用哪种方法，双指针的不行，因为树不能没有代价的从孩子节点找到父节点，那就使用OnePass加上HashTable解决，然后用基于循环的dfs进行遍历。

606. Construct String from Binary Tree

明显是一个先序遍历，没什么算法上的难度，就是逻辑理清了就行，主要看右节点有没有。右节点中存在，左节点一定加括号。右节点为空时，左节点非空时加括号。

590. N-ary Tree Postorder Traversal

没啥

404. Sum of Left Leaves

没啥。

538. Convert BST to Greater Tree

题目没啥，倒着中序遍历就行。用非递归的中序遍历来做可能更好，顺便用这道题复习非递归的中序遍历。然后还看到了一种Morris遍历法，不需要额外空间，下一题实现一下。

563. Binary Tree Tilt

后序遍历，用递归法是没有啥问题的，我想尝试用迭代的方法做这道题，没做出来。直接用迭代方式实现了一些树的迭代器在treetools中。

429. N-ary Tree Level Order Traversal

没啥

700. Search in a Binary Search Tree

没啥

543. Diameter of Binary Tree

没啥

589. N-ary Tree Preorder Traversal

没啥

107. Binary Tree Level Order Traversal II

没啥

671. Second Minimum Node In a Binary Tree

没啥

437. Path Sum III bangbang

关键是弄出了一个函数，计算以当前点为起点的解。

572. Subtree of Another Tree

我的思路是，两个树根节点一样就看看是不是一棵树，不一样就进s的左子树和t比，或者进s的右子树。

235. Lowest Common Ancestor of a Binary Search Tree

深度遍历，找到节点时保存各自的路径，然后返回最后一个相同的节点。但是注意是BST，直接可以选择进哪个节点。

501. Find Mode in Binary Search Tree

中序遍历得到非严格单增序列。

687. Longest Univalue Path

没啥

654. Maximum Binary Tree bangbang

我用的递归，就没啥。但是这道题不用递归就有难度了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def constructMaximumBinaryTree(self, nums):
    """
    :type nums: List[int]
    :rtype: TreeNode
    """
    stack = []
    for num in nums:
        cur = TreeNode(num)
        while stack and stack[-1].val < num:
        cur.left = stack.pop()
        
        if stack:
        stack[-1].right = cur
        stack.append(cur)
    return stack[0] if stack else None

230. Kth Smallest Element in s BST

中序遍历啊，没啥

814. Binary Tree Pruning

我的做法是先通过递归将树遍历一遍进行标记，标记的方式就利用TreeNode的val字段，然后在自顶向下的遍历树，把被标记的节点删除掉即可。没有考虑依次对被删除节点进行垃圾回收，是整个删除子树。

897. Increasing Order Search Tree

我过了的方法是中序遍历这棵树，新建一棵树，然后按照遍历的顺序不断地往这棵树中添加节点。然后看了看答案中较快的方法，是在原来的树上面修改指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def increasingBST(self, root):
        def changeOrder(node):
            if node:
                changeOrder(node.left)
                node.left = None
                self.cur.right = node
                self.cur = node
                changeOrder(node.right)

        res = self.cur = TreeNode(None)
        changeOrder(root)

        return res.right

508. Most Frequent Subtree Sum

后续递归（先递归子问题，然后解当前问题）。用一个字典缓存结果，然后遍历缓存。

894. All Possible Full Binary Trees

一看就是一个递归生成的问题，避免重复计算，自底向上生成。然后每一层只需要新建一个根节点，然后子树复用已经缓存的子树就行。

701. Insert into a Binary Search Tree

可以说是没有丝毫难度。

865. Smallest Subtree with all the Deepest Nodes

先遍历一遍确定树的深度以及最深的节点的个数。然后进行后递归，先判断左子树有几个最深节点，然后判断右子树有几个，然后加到一起如果等于总的就直接停止，否则返回当前最深节点数由父节点继续判断。

145. Binary Tree Postorder Traversal

虽然是hard级别，但是之前在别的题中写过非递归的后序遍历，因此不难。

95. Unique Binary Search Trees II

非常类似于894，但是这道题子树复用的可能性不大，因为子树结构不重复，我只复用的叶节点。

222. Count Complete Tree Nodes [bangbang]

这道题一看就是不能直接遍历，不然完全树的条件就没有用到。但是怎么用是一个问题，我已开始想的办法是深度有限遍历并且记录叶节点的深度，深度改变的时候就意味着最下面那一层的宽度，然后结合树的深度可以推出来总节点个数。
但是这种方法有一个问题，首先没有根本降低复杂度，对于n个结点的树，平均要遍历0.5n个节点才能得到答案，最坏情况是正好最后一层是满的，此时情况退化到需要遍历所有节点。抓住这一点进行优化，如果最后一层是满的，那么不需要遍历了，直到深度就行。那么在上面的算法中加上一个特殊情况的判断，树左边的深度等于右边的深度时，节点可以直接计算。
但是还是没有改变复杂度量级。考虑到完全二叉树的左右子树，中一定一颗是完全二叉树，另一颗是满的二叉树。那么就可以考虑用递归了，此时的复杂度是$$$O(logn)$$$。

337. House Robber III [bangbang]

这道题点赞数太多了，所以我也加了bangbang标签，但是感觉这道题实际上没有那么棒棒。就是一道把子问题的拆分方式都告诉你了的DP问题，每个点在子树已解决的情况下，尝试要么偷要么不偷。

102. Binary Tree Level Order Traversal

我用的双队列，import了collections中的deque，发现别人的代码格外的酷炫。

1
2
3
4
5
6
7
8
9
class Solution:
    def levelOrder(self, root):
        ans=[]
        level=[root]
        while level and root:
            ans.append([node.val for node in level])
            pair=[(node.left,node.right) for node in level]
            level=[kid for p in pair for kid in p if kid]
        return ans

236. Lowest Common Ancestor of a Binary Tree [bangbang]

又是一道上千赞的题目。而且剑指offer中又出现，在最后的第二个面试案例中。剑指offer中给的思路是如果树中有指向父节点的指针那就好办，变成两个链表找公共节点的问题，或者允许改动树，可以人为的改动指针这两种情况在这道题都不符合。然后剑指offer中给的最好的思路是保存根节点到这两个节点的路径，强行转化为找两个链表的公共节点。
然后我考虑到了一共可以避免这种额外的空间代价的方法。就是用两个flag，一个代表找到第一个节点，另一个代表找到第二个节点。然后后递归，如果连个flag均为真，就把那个节点返回。

652. Find Duplicate Subtrees [bangbang]

因为相似子树是基于递归的概念，当当两棵树的左子树和右子树和节点的值都一致的时候，认为两课子树是一致的。重要的是么通过递归函数的返回值判定两个子树是一致的。我想到的方法是制作一个哈希函数，整个树的哈希函数等于两棵子树的哈希值与当前节点值的哈希值的叠加，因为防止顺序颠倒，三个哈希值通过不一样的系数进行线性组合，然后对出现第二次的哈希值对应的子树进行存储。但是最后有一个测试用例通不过，不知道问什么。
然后看了答案的思路，总体思路也是用哈希值，但是不像我这么瞎弄哈希函数，而是对于新见到的树，用逐渐递增的索引值作为哈希值。思路很棒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import collections
class Solution(object):
    def findDuplicateSubtrees(self, root):
        trees = collections.defaultdict()
        trees.default_factory = trees.__len__
        count = collections.Counter()
        ans = []
        def lookup(node):
            if node:
                uid = trees[node.val, lookup(node.left), lookup(node.right)]
                count[uid] += 1
                if count[uid] == 2:
                    ans.append(node)
                return uid
        lookup(root)
        # print(trees)
        return ans

450. Delete Node in a BST

很基础的一道题但是比较考验基本功，需要找到被删除节点的上一个节点，用了两个trick。第一个是在树的根节点上面又加了一个父节点，起到类似于链表头结点的功能，第二个trick是类似于链表的删除，利用换值节省改变指针的操作。

623. Add One Row to Tree

没啥，就是层次遍历。

449. Serialize and Deserialize BST

我的方法就是对于BST来说，通过对树的前序和中序两种遍历方式可以还原一棵树这个性质来做。思路朴实，效率一般。然后考虑到leetcode有自己的序列化方法，这个我一开始想到这么做了，但是考虑到通过层次遍历的方法可能的问题是需要存空节点可能有空间浪费，但是我的方法也是需要存两倍的节点个数，空间点的个数最多不超多总的节点数（这种情况就是一棵右倾的树），所以从空间效率上两者不相上下。
但是时间效率和通用性上我的方法都略逊一筹。从时间效率的角度看，因为我的方法每次需要在中序遍历的数组中找到根节点，最坏情况就是一个左倾的树，此时是平方的复杂度。另外从通用性角度看，我的方法只适用于树中没有重复节点的情况，当左子树中有和根节点相同的值的时候，会导致在中序遍历的结果中不能判断哪一个是根节点。
这里给出标答：

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
from collections import deque
#serialize row by row, bfs
#for deserialization:
#the idea is to notice the pattern of distance of a node value to its children value
#write out a deserialized tree and notice, kinda intuitive
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        #go row by row, bfs
        q = deque([root])
        output = []
        while q:
            cur = q.popleft()
            output.append(str(cur.val) if isinstance(cur, TreeNode) else 'null')
            # only append children of a node, dont care about null
            if isinstance(cur, TreeNode):
                q.extend([cur.left, cur.right])
        # print(output)
        return ','.join(output) #seems like changing separator from ' ' to ',' passes more test case. y?
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        data = data.split()
        # take in an index where the value of node is in data list
        def create_node(i):
            if not i < len(data) or data[i] == 'null':
                return None
            node = TreeNode(data[i])
            dist_to_left_child = i+1
            node.left = create_node(i + dist_to_left_child)
            node.right = create_node(i + dist_to_left_child + 1)
            return node
            
        head = create_node(0) #create a node which has value at index = 0 in data
        return head

297. Serialize and Deserialize Binary Tree

基本上是按照层次遍历的思路。serialize的代码在上面已经有了，我自己写的基本和这段一致。但是deserialize的部分略有不同，因为serialize是连同None也会放到队列中，因此在序列化的结果中，相邻的两个一定是兄弟节点，这样的话就维护一个队列，这个队列中存放的都是还没有处理孩子节点的节点，然后每次从data中去两个元素转换成TreeNode，从队列中pop一个节点，把他们连上，然后把这两个孩子节点亚入队列，不断训练就可以。这样的话这个方法还可以推广到N叉树或者任意一棵树。

863. All Nodes Distance K in Binary Tree [bangbang]

这道题我拆成两部分来做。首先得到target节点的路径，用LR表示。这个本来想用非递归的形式写，没写出来，用递归好写多了。然后得到路径之后就好办了，此时考虑多种情况并用递归解决。
写一个递归函数，包含两个参数，一个是从当前节点出发，目标节点的路径，另一个是目标长度K。分三种情况，一种是当前节点是目标节点祖先（path不为空，K大于0,且len(path)==K），一种是目标节点是当前节点祖先（path为空，K=0），第三种是没有祖先关系(path为空，K=0)。后两个看似条件重复，但是实际上在进入左右子树的时候会区分开来。

919. Complete Binary Tree Inserter

用队列是一个很巧的方法，每次压两个出一个，停的时候可以保证queue中全部是叶子节点。

本站总访问量次