1.题目:在每个树行中找最大值

leetcode:515


这个是以空间换时间了，时间复杂度有所提高

func largestValues(root *TreeNode) []int {
    res := []int{}
    tmp := []int{}
    if root==nil{
        return res
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            tmp = append(tmp, node.Val)
        }
        m := max(tmp)
        res = append(res, m)
        tmp = []int{}
    }
    return res
}

func max(res []int)int{
    sort.Ints(res)
    var t int
    if len(res)!=0{
        t = res[len(res)-1]
    }
    return t
}

每次弹出节点的时候和最大值比较，大于则替换，
具体操作就是判断i,
如果等于0，max_val直接赋值node.val
如果i大于0说明不是第一个元素，就和max_val比较，大于则替换、

// 每次弹出节点的时候和最大值比较，大于则替换
func largestValues(root *TreeNode) []int {
    res := []int{}
    max_val := 0
    if root==nil{
        return res
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            // tmp = append(tmp, node.Val)
            if i>0{
                if node.Val>max_val{
                    max_val = node.Val
                }
            }else{
                max_val = node.Val
            }
        }
        res = append(res, max_val)
    }
    return res
}

2.题目2：填充每个节点的下一个右侧节点指针

leetcode:116

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    res := [][]*Node{}
    tmp := []*Node{}
    if root==nil{
        return root
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*Node)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            tmp = append(tmp, node)
        }
        res = append(res, tmp)
        tmp = []*Node{}
    }
    // 用来处理节点之间的关系
    for i:=0;i<len(res);i++{
        // j要是小于长度减一
        for j:=0;j<len(res[i])-1;j++{
            res[i][j].Next = res[i][j+1]
        }
    }
    return root
}

3.遍历每个节点下的右侧节点指针

leetcode:117

此处代码和上一题一样

4.二叉树最大深度

这道题也是套模板的题
leetcode104

func maxDepth(root *TreeNode) int {
    ret := 0
    if root==nil{
        return 0
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
        }
        ret ++
    }
    return ret
}

5.二叉树最小深度

leetcode:111

二叉树最小深度，也是用模板，主要是什么时候他是最小深度
答：左右节点全为空

func minDepth(root *TreeNode) int {
    depth := 0
    if root==nil{
        return 0
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            // 但当前节点没有左右节点的时候意味着他是最浅的
            if node.Left==nil&&node.Right==nil{
                return depth+1
            }
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
        }
        depth++
    }
    return depth
}