相同的树

相同的树

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
    }
}

简化了一下,其实之前有很多判断不用加

  1. 第二个大判断已经隐含表明,p 和 q 不同时是 nil 了,所以如果有一个是 nil 另一个肯定不是,肯定不相同
  2. 默认里面的那么多都可以省略,因为递归进去已经包含了
  3. 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
        }
    }
}

主要注意:

  1. 递归
  2. 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)
}