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
}