力扣刷题第二十八天--二叉树

前言

今天的五道题都是层序遍历的模板，深度优先的递归还不太熟。继续努力。

内容

一、在每个树行中找最大值

515.在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

广度优先搜素

时间复杂度：O(n)，其中 nnn 为二叉树节点个数，每一个节点仅会进出队列一次。

空间复杂度：O(n)，存储二叉树节点的空间开销。

func largestValues(root *TreeNode) []int {
     var res []int
    if root==nil{
        return res
    }//没有这个会panic: runtime error: invalid memory address or nil pointer dereference  
   
    curLevel:=[]*TreeNode{root}
    for len(curLevel)>0{
        nextLevel:=[]*TreeNode{}
        maxVal:=math.MinInt32
        for _,node:=range curLevel{
           
          maxVal= Max(maxVal,node.Val)
          if node.Left!=nil{
              nextLevel=append(nextLevel,node.Left)
          }
          if node.Right!=nil{
              nextLevel=append(nextLevel,node.Right)
          }
        }
        res=append(res,maxVal)
        curLevel=nextLevel
    }
    return res
}
 
func Max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

深度优先搜索

时间复杂度：O(n)，其中 nnn 为二叉树节点个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(height)。其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

func largestValues(root *TreeNode)(ans []int){
   var dfs func(*TreeNode,int)
   dfs=func(node *TreeNode,height int){
      if node==nil{
          return
      }
      if height==len(ans){
          ans=append(ans,node.Val)
      }else{
          ans[height]=max(ans[height],node.Val)
      }
      dfs(node.Left,height+1)
      dfs(node.Right,height+1)
   }
   dfs(root,0)
    
    return
}
func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

二、填充每个节点的下一个右侧节点指针

116.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

广度优先搜素

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */
 
func connect(root *Node) *Node {
    if root==nil{
        return root
    }
	curLevel:=[]*Node{root}
    for len(curLevel)>0{
        temp:=curLevel
        curLevel=nil
        for i,node:=range temp{
          if i+1<len(temp){
              node.Next=temp[i+1]
          }
          if node.Left!=nil{
              curLevel=append(curLevel,node.Left)
          }
           if node.Right!=nil{
              curLevel=append(curLevel,node.Right)
          }
        }
    }
    return root
}

使用已建立的next 指针 

时间复杂度：O(N)，每个节点只访问一次。

空间复杂度：O(1)，不需要存储额外的节点。

func connect(root *Node)*Node{
   if root==nil{
       return root
   }
    // 每次循环从该层的最左侧节点开始
   for leftmost:=root;leftmost.Left!=nil;leftmost=leftmost.Left{
       // 通过 Next 遍历这一层节点，为下一层的节点更新 Next 指针
       for node:=leftmost;node!=nil;node=node.Next{
           // 左节点指向右节点
           node.Left.Next=node.Right
           if node.Next!=nil{
               // 右节点指向下一个左节点
               node.Right.Next=node.Next.Left
           }
       }
   }
   return root
}

三、填充每个节点的下一个右侧节点指针II

117.填充每个节点的下一个右侧节点指针II

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

广度优先搜素

一模一样的代码 注意curLevel和temp 不要写混了

func connect(root *Node) *Node {
	if root==nil{
        return root
    }
    curLevel:=[]*Node{root}
    for len(curLevel)>0{
        temp:=curLevel
        curLevel=nil
        for i,node:=range temp{
            if i+1<len(temp){
                node.Next=temp[i+1]
            }
            if node.Left!=nil{
                curLevel=append(curLevel,node.Left)
            }
            if node.Right!=nil{
               curLevel=append(curLevel,node.Right)
            }
        }
    }
    return root
}

四、二叉树的最大深度

104.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

广度优先搜素

func maxDepth(root *TreeNode) int {
      var ans int
   if root==nil{
       return ans
   }
   curLevel:=[]*TreeNode{root}
   for len(curLevel)>0{
     temp:=curLevel
     curLevel=nil
       for _,node:=range temp{
          
           if node.Left!=nil{ 
               curLevel=append(curLevel,node.Left)
           }
           if node.Right!=nil{
               curLevel=append(curLevel,node.Right)
           }
       }
       ans++//记录深度，其他的是层序遍历的板子
       
   }
   return ans
}

深度优先搜索

func maxDepth(root *TreeNode)int{
    if root==nil{
        return 0
    }
    return max(maxDepth(root.Left),maxDepth(root.Right))+1
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

五、二叉树的最小深度

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

广度优先搜素

func minDepth(root *TreeNode) int {
   var ans int
   if root==nil{
       return ans
   }
   curLevel:=[]*TreeNode{root}
   for len(curLevel)>0{
     temp:=curLevel
     curLevel=nil
       for _,node:=range temp{
          if node.Left==nil&&node.Right==nil{
              return ans+1
          }
           if node.Left!=nil{ 
               curLevel=append(curLevel,node.Left)
           }
           if node.Right!=nil{
               curLevel=append(curLevel,node.Right)
           }
       }
       ans++
       
   }
   return ans
}

深度优先搜索

func minDepth(root *TreeNode)int{
  if root==nil{
      return 0
  }
  if root.Left==nil&&root.Right==nil{
      return 1
  }
  minD:=math.MaxInt32
  if root.Left!=nil{
      minD=min(minD,minDepth(root.Left))
  }
  if root.Right!=nil{
      minD=min(minD,minDepth(root.Right))
  }
  return minD+1
}
 
func min(a,b int)int{
    if a
        return a
    }
    return b
}

最后

即使感知自己身体的需求，不管是体力消耗还是脑力消耗，及时补充能量，吃饭，休息。