文章目录
- 71 · 二叉树的锯齿形层次遍历
- 650 · 二叉树叶子顺序遍历
- 69 · 二叉树的层次遍历
- 85 · 在二叉查找树中插入节点
- 93 · 平衡二叉树
71 · 二叉树的锯齿形层次遍历
给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
一开始想尝试下按照行的奇偶性质添加，但是不好使。又改了传统的bfs方法。黑猫白猫抓到耗子就是好猫。
from typing import (
List,
)
from lintcode import (
TreeNode,
)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
from collections import deque
class Solution:
"""
@param root: A Tree
@return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
"""
def zigzag_level_order(self, root: TreeNode) -> List[List[int]]:
# write your code here
if not root: return []
queue = deque([root])
tmp = []
while queue:
li = []
for _ in range(len(queue)):
node = queue.popleft()
li.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
tmp.append(li)
res = []
for index, i in enumerate(tmp):
if index % 2 == 0:
res.append(i)
else:
res.append(i[::-1])
return res
650 · 二叉树叶子顺序遍历
给定一个二叉树，像这样收集树节点：收集并移除所有叶子，重复，直到树为空。
这道题我想到用递归，找到最深的那个节点，如果是叶子节点，就加入到res里，然后将叶子节点变成None，返回。然后再看上一层节点。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: the root of binary tree
@return: collect and remove all leaves
"""
def findLeaves(self, root):
# write your code here
self.res = []
def dfs(self, root, li=[]):
if not root.left and not root.right:
li.append(root.val)
root = None
return
if root.left:
self.dfs(root.left, li)
if root.right:
self.dfs(root.right, li)
self.res.append(li)
下面是之前写的，之前写的也是参考了老师讲解的。现在看已经有点吃力了。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: the root of binary tree
@return: collect and remove all leaves
"""
def findLeaves(self, root):
# write your code here
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root is None:
return -1
left_level = self.dfs(root.left, res)
right_level = self.dfs(root.right, res)
current_level = max(left_level, right_level) + 1
self.add_into_res(current_level, res, root.val)
return current_level
def add_into_res(self, current_level, res, val):
if current_level == len(res):
res.append([])
res[current_level].append(val)
69 · 二叉树的层次遍历
给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）
from typing import (
List,
)
from lintcode import (
TreeNode,
)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
from collections import deque
class Solution:
"""
@param root: A Tree
@return: Level order a list of lists of integer
"""
def level_order(self, root: TreeNode) -> List[List[int]]:
# write your code here
if not root: return []
queue = deque([root])
res = []
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return res
终于碰到一道简单的。
85 · 在二叉查找树中插入节点
给定一棵二叉查找树和一个新的树节点，将节点插入到树中。
你需要保证该树仍然是一棵二叉查找树。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary search tree.
@param: node: insert this node into the binary search tree
@return: The root of the new binary search tree.
"""
def insertNode(self, root, node):
# write your code here
if not root:
return node
root = self.dfs(root, node)
return root
def dfs(self, root, node):
if not root:
return node
if node.val < root.val:
root.left = self.dfs(root.left, node)
elif node.val > root.val:
root.right = self.dfs(root.right, node)
return root
下面是我之前写的
def insertNode(self, root, node):
# write your code here
if root is None:
return node
if node.val < root.val:
root.left = self.insertNode(root.left, node)
if node.val > root.val:
root.right = self.insertNode(root.right, node)
return root
93 · 平衡二叉树
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
没写对
from lintcode import (
TreeNode,
)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: True if this Binary tree is Balanced, or false.
"""
def is_balanced(self, root: TreeNode) -> bool:
# write your code here
if not root: return True
depth = 1
return self.dfs(root, depth)
def dfs(self, root, depth):
if not root.left and not root.right:
return depth
left_depth, right_depth = -1, -1
if root.left:
left_depth = self.dfs(root.left, depth + 1)
if root.right:
right_depth = self.dfs(root.right, depth + 1)
return False if abs(left_depth - right_depth) > 1 else True
下面是官方答案，发现我上次也没写出来
class Solution:
"""
@param root: The root of binary tree.
@return: True if this Binary tree is Balanced, or false.
"""
def isBalanced(self, root):
is_balanced, _ = self.helper(root)
return is_balanced
def helper(self, root):
if not root:
return True, 0
is_left_balanced, left_height = self.helper(root.left)
is_right_balanced, right_height = self.helper(root.right)
root_height = max(left_height, right_height) + 1
if not is_left_balanced or not is_right_balanced:
return False, root_height
if abs(left_height - right_height) > 1:
return False, root_height
return True, root_height
