LeetCode 树相关 01

相同的树

相同的树

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