作者：青云算法
来源：https://blog.csdn.net/QingyunAlgo/article/details/86302835
分析：
这是LeetCode的第951题。
按照题目中翻转等价的定义，如果两棵二叉树翻转等价，那么首先它们的根节点要相同。如果根节点不同，那么两棵二叉树一定不是翻转等价。
接下来看左右子树是否翻转等价。这里要分两种情况讨论。第一种可能是不用交换根节点的左右子树，此时分别判断第一棵树的左子树和第二棵树的左子树是否翻转等价，以及第一棵树的右子树和第二棵树的右子树是否翻转等价。第二种可能是需要交换根节点的左右子树，此时分别判断第一棵树的左子树和第二棵树的右子树是否翻转等价，以及第一棵树的右子树和第二棵树的左子树是否翻转等价。
怎么判断子树翻转等价？这和判断整棵树翻转等价是同一个问题，可以递归解决。参考代码如下：
由于需要遍历整棵树，因此时间复杂度是O(n)，n为二叉树中节点的数目。
分享到:
閱讀更多 程序員聖經 的文章
