算法笔记-go-树

树的话基本都会使用到递归，递归最主要注意返回值和递归条件

如leetcode： https://leetcode.cn/problems/check-balance-lcci/?favorite=xb9lfcwi

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

算法如下


/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {

  res := true
  var getAlv func(*TreeNode) float64
  getAlv = func(node *TreeNode) float64 {
      if node == nil {
          return 0
      }
      if node != nil && node.Left == nil && node.Right == nil {
          return 1
      }
      curl := getAlv(node.Left)
      righl := getAlv(node.Right)
      cur := curl - righl
      if cur > 1 || cur < -1 {
          res = false
      }
      return math.Max(curl, righl) + 1
  }
  getAlv(root)
  return res
}

func isBalanced2(root *TreeNode) bool {
  if root == nil {
      return true
  }
  if math.Abs(depth(root.Left)-depth(root.Right)) < 1 {
      return isBalanced2(root.Left) && isBalanced(root.Right)
  }
  return false
}

func depth(root *TreeNode) float64 {
  if root == nil {
      return 0
  }
  return math.Max(depth(root.Left), depth(root.Right)) + 1
}

这里使用了两种方式去解这个题，depth就是递归函数，主要计算深度，isbalance也是递归，判断是否平衡

算法笔记-go-树

推荐阅读更多精彩内容