预备知识
【来自维基百科】二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
Trim a Binary Search Tree
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
一刷：Python
根据二叉寻找树的性质，在节点上的值可能会落在三个区间内（[-infinit, L), [L, R], (R, infinit)）若：
- 根节点上的值小于L，那么左侧的分枝就应该被砍掉，因此只需返回右侧分枝并将其作为新的根节点，然后继续查找即可
- 根节点上的值大于R，那么右侧的分枝就应该被砍掉，因此只需要返回左侧分枝并将其作为新的根节点，然后继续查找即可
- 若根节点的值在[L,R]之间，那么应该返回的是这整个节点，并继续查找左右两侧的分枝.
- 若该节点上值不存在，返回None.
class Solution(object):
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if not root:
return None
elif root.val > R:
# root = root.right
return self.trimBST(root.left, L, R)
elif root.val < L:
# root = root.left
return self.trimBST(root.right, L, R)
root.right = self.trimBST(root.right,L, R )
root.left = self.trimBST(root.left, L, R)
return root
此题还可以使用了python在函数内嵌套定义函数：
原作sth4nothing的答案
def trimBST(self, root, L, R):
def trim(node):
if node:
if node.val > R:
return trim(node.left)
elif node.val < L:
return trim(node.right)
else:
node.left = trim(node.left)
node.right = trim(node.right)
return node
return trim(root)
Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
一刷：Python
一刷写的方法比较丑，是构建了一个dict，用depth做key，将value初始化为list，append进每一层的根/叶节点上的值：
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
visited_dict = {}
def search_tree(node, depth = 0):
if not node:
return
if depth not in visited_dict.keys():
visited_dict[depth] = []
visited_dict[depth].append(node.val)
if node.left or node.right:
depth += 1
if depth not in visited_dict.keys():
visited_dict[depth] = []
search_tree(node.left, depth)
search_tree(node.right, depth)
return
import numpy as np
search_tree(root, depth = 0)
return map(lambda x: float(np.mean(x)), visited_dict.values())
但此方法较慢，考虑了一波优化，将dict改为defaultdict，并用内置函数求average，速度加快（主要是不调用numpy的mean使得时间大幅加快）
from collections import defaultdict
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
visited_dict = defaultdict(list)
def search_tree(node, depth = 0):
if not node:
return
visited_dict[depth].append(node.val)
if node.left or node.right:
depth += 1
search_tree(node.left, depth)
search_tree(node.right, depth)
return
search_tree(root, depth = 0)
return map(lambda x: float(sum(x))/len(x), visited_dict.values())
此方法存贮量也大，其实只需记录每一层的sum以及节点个数即可，继续优化一波
from collections import defaultdict
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
visited_dict = defaultdict(list)
def search_tree(node, depth = 0):
if not node:
return
if visited_dict[depth] == []:
visited_dict[depth].extend([0,0])
# print visited_dict
visited_dict[depth][0] += 1
visited_dict[depth][1] += node.val
if node.left or node.right:
depth += 1
search_tree(node.left, depth)
search_tree(node.right, depth)
return
search_tree(root, depth = 0)
return map(lambda x: float(x[1])/x[0], visited_dict.values())
但此方法时间反而变慢了【122s】
Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
一刷：Python
思路：先处理边界情况：
- 若节点为空，直接返回
- 若左右两颗树中一颗为空，则返回非空的那个
- 若左右两颗树都不为空：
首先创建一个新的根节点，val为两者根节点上val的加和
其次，在这个新的根节点的左右子树上递归合并两者的左右子树
# 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 mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if not t1 and not t2:
return
if not t1:
merge_tree = t2
elif not t2:
merge_tree = t1
else:
merge_tree = TreeNode(t1.val+t2.val)
merge_tree.right = self.mergeTrees(t1.right, t2.right)
merge_tree.left = self.mergeTrees(t1.left, t2.left)
return merge_tree
