[数据结构与算法]剑指 Offer 27. 二叉树的镜像

剑指 Offer 27. 二叉树的镜像?
?

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

?????4
???/ ??\
??2 ????7
?/ \? ? ?/ \
1 ??3 6 ??9
镜像输出：

?????4
???/ ??\
??7 ????2
?/ \? ? ?/ \
9 ??6 3???1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
?

限制：

0 <= 节点个数 <= 1000

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

思路：
参考题解：LeetCode大佬题解?

时间复杂度 ：
O(MN)，其中 M,N 分别为树 A?和 树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用 recur(A, B) 判断占用 O(N) 。
?

空间复杂度 O(M) ：
当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M≤N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 题解：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil {
        return false
    }

   if myIsSubTree(A, B) {
       return true
   }

   return isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func myIsSubTree(A *TreeNode, B *TreeNode) bool {
    if B == nil { // 注意：这里要先判断 B == nil，再判断 A == nil，否则结果错误！ ???
        return true
    }

    if A == nil {
        return false
    }
    
    if A.Val != B.Val {
        return false
    }

    return myIsSubTree(A.Left, B.Left) && myIsSubTree(A.Right, B.Right)
}