day13
一:层序遍历:即依据根左右继续左右依层遍历各节点
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = collections.deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
result.append(level)
return result
"递归法"
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
self.helper(root,0,levels)
return levels
def helper(self,node,level,levels):
if not node:
return
if len(levels) < level:
levels.append([])
levels[level].append(node.val)
self.helper(node.left,level+1,levels)
self.helper(node.right,level+1,levels)
func levelOrder(root *TreeNode) [][]int {
arr := [][]int{}
depth :=0
var order func(root *TreeNode,depth int)
order = func(root *TreeNode,depth int){
if root == nil{
return
}
if len(arr) == depth{
arr = append(arr,[]int{})
}
arr[depth] = append(arr[depth],root.Val)
order(root.Left,depth+1)
order(root.Right,depth+1)
}
order(root,depth)
return arr
}
//队列法
func levelOrder(root *TreeNode) [][]int {
res :=[][]int {}
if root == nil {
return res
}
queue :=list.New()
queue.PushBack(root)
var tmpArr []int
for queue.Len() > 0{
length :=queue.Len()
for i:=0;i<length;i++{
//前弹出节点,此时为root
node := queue.Remove(queue.Front()).(*TreeNode)
//然后是左右
if node.Left != nil{
queue.PushBack(node.Left)
}
if node.Right != nil{
queue.PushBack(node.Right)
}
//将node的值加入tmpArr中
tmpArr = append(tmpArr,node.Val)
}
//再将所需结果加入res
res = append(res,tmpArr)
tmpArr = []int{}
}
return res
}
第二题层序遍历之二:
要求从叶子到根反向遍历
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
"借用dequeue将root装入"
queue = collections.deque([root])
result = []
while queue:
level = []
"遍历途中不断将队列左弹出并将值加入level再遍历左右"
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
"将level加入result里"
result.append(level)
"最后反转"
return result[::-1]
//go语言原理同上
func levelOrderBottom(root *TreeNode) [][]int {
queue := list.New()
res := [][]int{}
if root == nil {
return res
}
queue.PushBack(root)
for queue.Len() > 0 {
length := queue.Len()
tmp :=[]int{}
for i:=0;i<length;i++{
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil{
queue.PushBack(node.Left)
}
if node.Right != nil{
queue.PushBack(node.Right)
}
tmp = append(tmp,node.Val)
}
res = append(res,tmp)
}
for i:=0;i<len(res) / 2;i++ {
res[i],res[len(res) -i -1] = res[len(res) -i -1 ],res[i]
}
return res
}
第三题:二叉树之右视图,即幻想在二叉树右侧观察节点
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = collections.deque([root])
right_view = []
"先读根,再由于队列中长度即为所有节点总数,"
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
right_view.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return right_view
func rightSideView(root *TreeNode) []int {
if root == nil {
return nil
}
//先层序遍历再取每层最后一个元素即最右边的
res := make([]int,0)
queue := list.New()
queue.PushBack(root)
for queue.Len() > 0{
length := queue.Len()
for i:=0;i<length;i++{
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil{
queue.PushBack(node.Left)
}
if node.Right != nil{
queue.PushBack(node.Right)
}
if i == length - 1 {
res = append(res,node.Val)
}
}
}
return res
}
第四题:
求二叉树每层的平均值
原理实际上是层序遍历时每次求和求平均值
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
if not root:
return []
queue = collections.deque([root])
averages = []
while queue:
size = len(queue)
level_sum = 0
for i in range(size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
averages.append(level_sum / size)
return averages
func averageOfLevels(root *TreeNode) []float64 {
if root == nil {
return nil
}
res := make([]float64,0)
queue := list.New()
queue.PushBack(root)
var sum int
for queue.Len() > 0{
length := queue.Len()
for i:=0;i<length;i++{
node := queue.Remove(queue.Front()).(*TreeNode)
if node.Left != nil{
queue.PushBack(node.Left)
}
if node.Right != nil{
queue.PushBack(node.Right)
}
sum += node.Val
}
res = append(res,float64(sum) / float64(length))
//每层需要被清空
sum = 0
}
return res
}
第五题:N叉树的层序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
result = []
queue = collections.deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
"遍历孩子并不断将其加入queue中,使得上层循环中不断访问节点值并最终得到结果集"
for child in node.children:
queue.append(child)
result.append(level)
return result
"递归法不是很熟悉"
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
result = []
def travelsal(root,depth):
if len(result) == depth:
result.append([])
result[depth].append(root.val)
if root.children:
for i in range(len(root.children)):
travelsal(root.children[i],depth+1)
travelsal(root,0)
return result
func levelOrder(root *Node) [][]int {
queue := list.New()
res := [][]int{}
if root == nil {
return res
}
queue.PushBack(root)
for queue.Len() > 0{
length := queue.Len()
var tmp []int
for T :=0;T < length;T++{
myNode := queue.Remove(queue.Front()).(*Node)
tmp = append(tmp,myNode.Val)
for i:=0;i<len(myNode.Children);i++{
queue.PushBack(myNode.Children[i])
}
}
res = append(res,tmp)
}
return res
}
题目六:在每个二叉树行中找最大值
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
result = []
queue = collections.deque([root])
while queue:
level_size = len(queue)
max_val = float('-inf')
for _ in range(level_size):
node = queue.popleft()
max_val = max(max_val,node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(max_val)
return result
func largestValues(root *TreeNode) []int {
if root == nil {
return nil
}
queue := list.New()
queue.PushBack(root)
ans := make([]int,0)
temp := math.MinInt64
for queue.Len() >0{
length := queue.Len()
for i:=0;i<length;i++{
node := queue.Remove(queue.Front()).(*TreeNode)
temp = max(temp,node.Val)
if node.Left != nil{
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
}
ans = append(ans,temp)
temp = math.MinInt64
}
return ans
}
func max(x,y int) int {
if x > y{
return x
}
return y
}
题目七 侧节点指针的填充
给定一个完美二叉树每个节点都有两个字节点
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return root
queue = collections.deque([root])
while queue:
level_size = len(queue)
prev = None
for i in range(level_size):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
func connect(root *Node) *Node {
if root == nil {
return root
}
queue := list.New()
queue.PushBack(root)
tempArr :=make([]*Node,0)
for queue.Len() > 0{
length := queue.Len()
for i:=0;i<length;i++{
node := queue.Remove(queue.Front()).(*Node)
if node.Left != nil{
queue.PushBack(node.Left)
}
if node.Right != nil{
queue.PushBack(node.Right)
}
tempArr = append(tempArr,node)
}
if len(tempArr) > 1 {
for i:=0;i<len(tempArr)-1;i++{
tempArr[i].Next = tempArr[i+1]
}
}
tempArr = []*Node{}
}
return root
}
题目八与上题本质上没区别
题目九:反转二叉树
"遍历法,前中后序遍历交换指针即可"
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left,root.left = root.right,root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
"广度优先遍历,并交换指针"
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
for i in range(len(queue)):
node = queue.popleft()
node.left,node.right = node.right,node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
//前序的递归
func invertTree(root *TreeNode) *TreeNode {
if root == nil{
return nil
}
root.Left,root.Right = root.Right,root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
queue := list.New()
node := root
queue.PushBack(node)
for queue.Len() > 0{
length := queue.Len()
for i:=0;i<length;i++{
e := queue.Remove(queue.Front()).(*TreeNode)
e.Left,e.Right = e.Right,e.Left
if e.Left != nil {
queue.PushBack(e.Left)
}
if e.Right != nil{
queue.PushBack(e.Right)
}
}
}
return root
}
题目十:判断二叉树是否对称
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.compare(root.left,root.right)
def compare(self,left,right):
if left == None and right != None:
return False
elif left != None and right == None:
return False
elif left == None and right== None:
return True
elif left.val != right.val:
return False
outside = self.compare(left.left,right.right)
inside = self.compare(left.right,right.left)
isSame = outside and inside
return isSame
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
queue = collections.deque([root.left,root.right])
while queue:
level_size = len(queue)
if level_size % 2 != 0:
return False
level_vals = []
for i in range(level_size):
node = queue.popleft()
if node:
level_vals.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
level_vals.append(None)
if level_vals != level_vals[::-1]:
return False
return True
func defs(left *TreeNode,right *TreeNode)bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
if left.Val != right.Val{
return false
}
return defs(left.Left,right.Right) && defs(right.Left,left.Right)
}
func isSymmetric(root *TreeNode) bool {
return defs(root.Left,root.Right)
}
func isSymmetric(root *TreeNode) bool {
var queue []*TreeNode
if root != nil {
queue = append(queue,root.Left,root.Right)
}
for len(queue) > 0{
left :=queue[0]
right :=queue[1]
queue = queue[2:]
if left == nil && right == nil{
continue
}
if left == nil || right == nil || left.Val != right.Val{
return false
}
queue = append(queue,left.Left,right.Right,right.Left,left.Right)
}
return true
}
标签:node,right,return,queue,day13,root,left
From: https://www.cnblogs.com/leisure535/p/18242638