开心一刻
语文诗歌题三大基本方法：诗人被贬法，诗人开心法，诗人思乡法。
数学做题三大基本方法：肉眼观察法，暴力代值法，显然成立法。
英语阅读题三大基本方法：硬币投掷法，笔尖坠落指向法，投骰法。
物理做题三大基本方法：直接代公式法，保守少选法，一看就不对法。
政治大题三大基本方法：照搬材料原文法，照搬选择题干法，照搬选择选项法。
历史史论题三大基本方法：他说的有理法，他说的片面法，他说的扯淡法。
地理做题三大基本方法：看地图法，画地图法，创造地图法。
最近面试被问到二叉树的相关问题, 有的没有回答好, 趁此机会记录一些网上常见的面试题目, 做些总结。
二叉树的结构
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
求二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
算法思路：节点为空时，返回节点深度为0；递归计算左右子树的深度，然后用较大值加上父节点的深度1；然后返回，最终返回到根节点时即可求得最大深度。
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
var left = maxDepth(root.Left)
var right = maxDepth(root.Right)
if left > right {
return left + 1
}
return right + 1
}
求二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
算法思路：根节点需要特殊判断，为空时返回深度为0；对于叶子节点，不计算叶子节点的左右子树深度，而是直接返回深度为1；对于只有左子树的节点，左子树深度标记为不可达，只有右子树的节点同理；然后计算左右子树的最小深度，用最小深度加上父节点的深度1
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
return getMin(root)
}
func getMin(root *TreeNode) int {
if root == nil {
return int(^uint(0) >> 1)
}
if root.Left == nil && root.Right == nil {
return 1
}
return Min(getMin(root.Left), getMin(root.Right)) + 1
}
func Min(x, y int) int {
if x > y {
return y
}
return x
}
求二叉树中节点的个数
算法思路：递归计算左右子树节点个数后，返回左右子树节点个数和父节点个数的和即可
func numOfTreeNode(root *TreeNode) int {
if root == nil {
return 0
}
var left = numOfTreeNode(root.Left)
var right = numOfTreeNode(root.Right)
return left + right + 1
}
求二叉树中叶子节点的个数
算法思路：叶子节点需要单独判断，并返回结果1；然后递归计算左子树叶子节点数量和右子树叶子节点数量，然后相加并返回
func numOfNoChildNode(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 1
}
var left = numOfTreeNode(root.Left)
var right = numOfTreeNode(root.Right)
return left + right
}
判断二叉树是否是平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
算法思路：判断是否是平衡二叉树属于求树的最大深度的变种。当判断某一节点的左右子树的深度之差的绝对值大于1时，那么整棵二叉树就不是平衡二叉树了，所以在此时可以返回一个特殊值来标记（此处用的-1，因为求二叉树深度不可能出现负值），那么最终的结果也会是这个特殊值，根据这个特殊值就可以判断这个二叉树是否是一个平衡二叉树。
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
return getDepth(root) != -1
}
func getDepth(root *TreeNode) int {
if root == nil {
return 0
}
var left = getDepth(root.Left)
var right = getDepth(root.Right)
if left == -1 || right == -1 || Abs(left, right) > 1 {
return -1
}
if left > right {
return left + 1
} else {
return right + 1
}
}
func Abs(x, y int) int {
if x > y {
return x - y
} else {
return y - x
}
}
求二叉树中第K层节点的个数
与求叶子节点的数量相似, 只不过判断叶子节点的时候修改成判断当前k是否为1
func numOfKLevelNode(root *TreeNode, k int) int {
if root == nil {
return 0
}
if k == 1 {
return 1
}
var left = numOfKLevelNode(root.Left, k - 1)
var right = numOfKLevelNode(root.Right, k - 1)
return left + right
}
判断二叉树是否是完全二叉树
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2^h 个节点。）
根据完全二叉树的定义, 使用层次遍历即可解决.
func isCompleteTree(root *TreeNode) bool {
if root == nil {
return true
}
var queue = []*TreeNode{root}
var num = 1
for i := 0; len(queue) != 0; i++ {
var q []*TreeNode
var flag bool
for j := 0; j < len(queue); j++ {
node := queue[j]
if flag && node.Left != nil {
return false
}
if node.Left != nil {
q = append(q, node.Left)
} else {
flag = true
}
if flag && node.Right != nil {
return false
}
if node.Right != nil {
q = append(q, node.Right)
} else {
flag = true
}
}
if len(q) != 0 {
if len(queue) != num {
return false
}
num *= 2
}
queue = q
}
return true
}
两个二叉树是否完全相同
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil || p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
两个二叉树是否互为镜像
func isMirror(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil || p.Val != q.Val {
return false
}
return isMirror(p.Left, q.Right) && isSameTree(p.Right, q.Left)
}
翻转二叉树or镜像二叉树
func mirrorTree(root *TreeNode) *TreeNode {
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
dfs(root.Right)
root.Left, root.Right = root.Right, root.Left
}
dfs(root)
return root
}
二叉树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
if root.Val == p.Val || root.Val == q.Val {
return root
}
var left = lowestCommonAncestor(root.Left, p, q)
var right = lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left == nil {
return right
}
return left
}
二叉树的前序遍历
func preorderTraversal(root *TreeNode) []int {
var ret []int
var preorder func(root *TreeNode)
preorder = func(root *TreeNode) {
if root == nil {
return
}
ret = append(ret, root.Val)
preorder(root.Left)
preorder(root.Right)
}
preorder(root)
return ret
}
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
var ret []int
var stack = []*TreeNode{root}
for len(stack) != 0 {
node := stack[len(stack) - 1]
stack = stack[: len(stack) - 1]
ret = append(ret, node.Val)
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return ret
}
二叉树的中序遍历
func inorderTraversal(root *TreeNode) []int {
var ret []int
var inorder func(root *TreeNode)
inorder = func(root *TreeNode) {
if root == nil {
return
}
inorder(root.Left)
ret = append(ret, root.Val)
inorder(root.Right)
}
inorder(root)
return ret
}
func inorderTraversal(root *TreeNode) []int {
var (
ret []int
stack []*TreeNode
cur *TreeNode
)
cur = root
for len(stack) != 0 || cur != nil {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
node := stack[len(stack) - 1]
stack = stack[: len(stack) - 1]
ret = append(ret, node.Val)
cur = node.Right
}
return ret
}
二叉树的后序遍历
func postorderTraversal(root *TreeNode) []int {
var ret []int
var postorder func(root *TreeNode)
postorder = func(root *TreeNode) {
if root == nil {
return
}
postorder(root.Left)
postorder(root.Right)
ret = append(ret, root.Val)
}
postorder(root)
return ret
}
func postorderTraversal(root *TreeNode) []int {
var (
ret []int
stack1 []*TreeNode
)
if root == nil {
return nil
}
stack1 = append(stack1, root)
for len(stack1) != 0 {
node := stack1[len(stack1) - 1]
stack1 = stack1[: len(stack1) - 1]
ret = append(ret, node.Val)
if node.Left != nil {
stack1 = append(stack1, node.Left)
}
if node.Right != nil {
stack1 = append(stack1, node.Right)
}
}
for i, j := 0, len(ret) - 1; i < j; i, j = i + 1, j - 1 {
ret[i], ret[j] = ret[j], ret[i]
}
return ret
}
二叉树中路径和为k的路径
func pathSum(root *TreeNode, targetSum int) [][]int {
var (
ret [][]int
path []int
)
var dfs func(root *TreeNode, target int)
dfs = func(root *TreeNode, target int) {
if root == nil {
return
}
if root.Left == nil && root.Right == nil {
if root.Val == target {
tmp := append(path, target)
ret = append(ret, append([]int(nil), tmp...))
}
return
}
path = append(path, root.Val)
dfs(root.Left, target - root.Val)
dfs(root.Right, target - root.Val)
path = path[: len(path) - 1]
}
dfs(root, targetSum)
return ret
}
二叉树层次遍历
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var queue = []*TreeNode{root}
var ret [][]int
for i := 0; len(queue) != 0; i++ {
var q []*TreeNode
ret = append(ret, []int(nil))
for j := 0; j < len(queue); j++ {
node := queue[j]
ret[i] = append(ret[i], node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
queue = q
}
return ret
}
判断二叉树是否是合法的二叉查找树
func isValidBST(root *TreeNode) bool {
left, right := math.MinInt64, math.MaxInt64
var in_order func(root *TreeNode, left, right int) bool
in_order = func(root *TreeNode, left, right int) bool {
if root == nil {
return true
}
if left >= root.Val || root.Val >= right {
return false
}
return in_order(root.Left, left, root.Val) && in_order(root.Right, root.Val, right)
}
return in_order(root, left, right)
}
func isValidBST(root *TreeNode) bool {
var (
stack []*TreeNode
cur *TreeNode
pre int
)
if root == nil {
return true
}
pre = -1 << 63
cur = root
for cur != nil || len(stack) != 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
node := stack[len(stack) - 1]
stack = stack[: len(stack) - 1]
cur = node.Right
if pre >= node.Val {
return false
}
pre = node.Val
}
return true
}