TagTree

Serialize&Deserialize.png

# 297. Serialize and Deserialize Binary Tree
class Codec:
    def serialize(self,root):
        def doit(node): # 每次调用 传入节点
            if node:
                vals.append(str(node.val)) # 要转字符
                doit(node.left)  #左右也是处理节点
                doit(node.right) 
            else:
                vals.append('#') # 至叶子节点 标记一条路径
        vals=[] #
        doit(root)
        return ' '.join(vals) # 迭代生成整棵树的数组 转为串儿
    
    def deserialize(self,data):
        def doit():  # 没有参数 next迭代生成参数 参数不能直接传递 是需要next方法生成 
            val=next(vals) # next读取/生成当前节点字符 Python直接用变量不用定义
            if val=='#': return None # Tree的叶子结点一条路径结束 
            node=TreeNode(val) # Tree的生成
            node.left=doit() #因为递归 一条终结 可以继续上一层的doit
            node.right=doit()
            return node
        # 递归方法封起来 在反序列中递归调用该方法
        vals=iter(data.split()) #迭代对象为每个节点字符
        return doit()

Mini Cost Tree.png

# Mini Cost Tree From Leaf Values <== Leaf
# In:  arr[]; leaf In-order; 
# Out ==> Product Largest L&R; smallest sum;
class Solution:
    def mctFromLeafValues(self, A):
        res, n = 0, len(A)
        stack = [float('inf')]
        for a in A:
            while stack[-1] <= a:
                mid = stack.pop()
                res += mid * min(stack[-1], a)
            stack.append(a)
        while len(stack) > 2:
            res += stack.pop() * stack[-1]
        return res

BT maxPathSum.png

# 124. Binary Tree Maximum Path Sum
# non-empty binary tree, find the maximum path sum.
# parent-child connections.
# contain at least one node;
class Solution:
     # parent-child connections.
    def maxPathSum(self, root):
        def maxend(node):
            if not node: return 0
            left = maxend(node.left)
            right = maxend(node.right)
            self.max = max(self.max, left + node.val + right)
            return max(node.val + max(left, right), 0)
        self.max = 0
        maxend(root)
        return self.max

BT Right Side View.png

# 199. Binary Tree Right Side View
# Given a binary tree, right side of it
# ==>values of the nodes ordered from top to bottom.
class Solution:
    def rightSideView(self,root):
        def collect(node,depth):
            if node:
                if depth==len(view):
                    view.append(node.val)
                collect(node.right,depth+1)
                collect(node.left,depth+1)
        view=[]
        collect(root,0)
        return view

Subtree.png

# 572. Subtree of Another Tree
# two non-empty binary trees s and t, 
# check whether tree t has exactly the same structure and node values with a subtree of s.
# A subtree of s is a tree consists of a node in s and all of this node's descendants. 
# The tree s could also be considered as a subtree of itself.
 
class Solution(object):    
    def isMatch(self, s, t):
        if not(s and t):
            return s is t
        return (s.val == t.val and 
                self.isMatch(s.left, t.left) and 
                self.isMatch(s.right, t.right))   

    def isSubtree(self, s, t):
        if self.isMatch(s, t): return True
        if not s: return False
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)