相同的树
update:
func isSameTree(p *TreeNode, q *TreeNode) bool { if p == nil && q == nil { return true } else if p == nil || q == nil { return false } else { if p.Val == q.Val { return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right) } return false } }
简化了一下,其实之前有很多判断不用加
- 第二个大判断已经隐含表明,p 和 q 不同时是 nil 了,所以如果有一个是 nil 另一个肯定不是,肯定不相同
- 默认里面的那么多都可以省略,因为递归进去已经包含了
- 00 01 10 11 四种情况,能进入下面的判断,本身说明上面的判断不满足,这里的逻辑简化要注意
func isSameTree(p *TreeNode, q *TreeNode) bool { if p == nil && q == nil { return true } else if p == nil && q != nil || p != nil && q == nil { return false } else { if p.Val == q.Val { if p.Right == nil && q.Right != nil || p.Right != nil && q.Right == nil || p.Left == nil && q.Left != nil || p.Left != nil && q.Left == nil { return false } else if p.Right == nil && q.Right == nil { return isSameTree(p.Left, q.Left) } else if p.Left == nil && q.Left == nil { return isSameTree(p.Right, q.Right) } else { return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right) } } else { return false } } }
主要注意:
- 递归
- corner case 比较多,小心注意
二叉树的最大深度
func maxDepth(root *TreeNode) int { if root == nil { return 0 } else { rDepth := maxDepth(root.Right) lDepth := maxDepth(root.Left) if rDepth > lDepth { return 1 + rDepth } else { return 1 + lDepth } } }
二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
func minDepth(root *TreeNode) int { if root == nil { return 0 } else { rDepth := minDepth(root.Right) lDepth := minDepth(root.Left) if rDepth == 0 { return 1 + lDepth } else if lDepth == 0 { return 1 + rDepth } else if rDepth < lDepth { return 1 + rDepth } else { return 1 + lDepth } } }
高度平衡二叉树
一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
func isBalanced(root *TreeNode) bool { if root == nil { return true } else { return maxHeight(root.Left) - maxHeight(root.Right) >= -1 && maxHeight(root.Left) - maxHeight(root.Right) <= 1 && isBalanced(root.Left) && isBalanced(root.Right) } } func maxHeight(root *TreeNode) int { if root == nil { return 0 } else { rH := maxHeight(root.Right) lH := maxHeight(root.Left) if rH > lH { return 1 + rH } else { return 1 + lH } } }
二叉树遍历
二叉树的前、中、后序遍历,这里的前(pre)、中(in)、后(post)是 根结点值 root.Val 相对于 左子树和右子树的位置。
二叉树中序遍历
func inorderTraversal(root *TreeNode) []int { if root == nil { return []int{} } lans := inorderTraversal(root.Left) rans := inorderTraversal(root.Right) return append(append(lans, root.Val), rans...) }
二叉树前序遍历
func preorderTraversal(root *TreeNode) []int { if root == nil { return []int{} } lans := preorderTraversal(root.Left) rans := preorderTraversal(root.Right) return append(append([]int{root.Val}, lans...), rans...) }
二叉树后序遍历
func postorderTraversal(root *TreeNode) []int { if root == nil { return []int{} } lans := postorderTraversal(root.Left) rans := postorderTraversal(root.Right) return append(append(lans, rans...), root.Val) }