526互联

代码随想录算法训练营第13天 | 树的层序遍历、lc226、lc101

发布时间 2023-12-31 23:08:26作者: geJoyo

（本合集全部为Go语言实现）

相关文章链接：层序遍历题解 226题解 101题解
相关视频链接：

Leetcode102

状态：迭代写法秒了，递归写法确实吗，没太能想到
实现过程中的难点：递归写法中，思想要转变。迭代写法是真正的按层遍历，递归写法是以类似深度优先的方式将遍历结果放到不同的层级的集合当中

个人写法

迭代写法

func levelOrder(root *TreeNode) [][]int {
  var res [][]int
  if (root == nil) {
    return res
  }
  
  var queue []*TreeNode
  offer := func(node *TreeNode) {
    queue = append(queue, node)
  }
  poll := func() *TreeNode {
    tmp := queue[0]
    queue = queue[1:]
    return tmp
  }

  offer(root)
  for len(queue) > 0 {
    size := len(queue)
    var curRes []int
    for size > 0 {
      curNode := poll()
      curRes = append(curRes, curNode.Val)
      if curNode.Left != nil {
        offer(curNode.Left)
      }
      if curNode.Right != nil {
        offer(curNode.Right)
      }
      size--
    }
    res = append(res, curRes)
  }
  return res
}

递归写法

func levelOrder(root *TreeNode) [][]int {
  var res [][]int
  levelOrder0(root, 0, &res)
  return res
}

func levelOrder0(root *TreeNode, depth int, res *([][]int)) {
  if root == nil {
    return
  }
  if len(*res) == depth {
    *res = append(*res, []int {})
  }
  (*res)[depth] = append((*res)[depth], root.Val)
  levelOrder0(root.Left, depth + 1, res)
  levelOrder0(root.Right, depth + 1, res)
}

Leetcode226

状态：
实现过程中的难点：

个人写法

func invertTree(root *TreeNode) *TreeNode {
  invertTree0(root)
  return root
}

func invertTree0(root *TreeNode) {
  if root == nil {
    return
  }
  root.Left, root.Right = root.Right, root.Left
  invertTree0(root.Left)
  invertTree0(root.Right)
}

Leetcode101

状态：
实现过程中的难点：

个人写法

type queue []*TreeNode

func (q *queue) offer(node *TreeNode) {
  *q = append(*q, node)
}

func (q *queue) poll() *TreeNode {
  tmp := (*q)[0]
  *q = (*q)[1:]
  return tmp
}

func isSymmetric(root *TreeNode) bool {
  if root == nil {
    return true
  }

  var q queue
  q.offer(root.Left)
  q.offer(root.Right)
  for len(q) > 0 {
    rNode := q.poll()
    lNode := q.poll()
    if lNode == nil && rNode == nil {
      continue
    } else if lNode != nil && rNode != nil {
      if lNode.Val != rNode.Val {
        return false
      }
      q.offer(lNode.Left)
      q.offer(rNode.Right)
      q.offer(lNode.Right)
      q.offer(rNode.Left)
    } else {
      return false
    }
  }
  return true
}

今日收获

  • 学会了层序遍历的递归方式

学习时长：2小时左右