BM31. [对称的二叉树]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM31. 对称的二叉树
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：
下面这棵二叉树是对称的
下面这棵二叉树不对称。
题目分析
还记得上次告诉你的东西吗？
从下到上就用后序遍历
从上到下就用前序遍历
带有顺序就用中序遍历
行有关系就用层序遍历
这道题目明显是和每行有关系，你可以想直接使用层序遍历好不好？直接套用层序遍历的模板，判断这一层是不是回文队列就可以了，但是这块要使用一个层序遍历的升级，比如牛客的oj系统默认给出的就是一种特殊层序遍历比如，将每层的空节点替换为特殊#，同理我们也是可以直接这样使用的。这样直接判断是不是层序遍历就可以了
{1,2,2,#,3,#,3} 明显 #,3,#,3就不是一个回文list
直接上升级的层序遍历模板
增加一个特殊的#值，比如这块题目给到要求是数据范围：节点数满足 0≤n≤1000，节点上的值满足 0∣v*a*l∣≤1000，我们直接给特殊值int作为#即可比如Integer.MIN_VALUE，这块需要注意下就是因为要把左右节点加入进去但是我们自己构造的空节点是没有左右节点的需要判断一下不要再判断空节点的左右节点即可。
boolean isSymmetrical(TreeNode root) {
TreeNode emptyTreeNode = new TreeNode(Integer.MIN_VALUE);
if (root == null) {
return true;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
//while的一次循环遍历就必须吃掉里面所有的内容
while (!queue.isEmpty()) {
int count = queue.size();
ArrayList<Integer> rowList = new ArrayList<Integer>();
while (count > 0) {
TreeNode curr = queue.poll();
//因为要把左右节点加入进去但是我们自己构造的空节点是没有左右节点的需要判断一下不要再判断空节点的左右节点即可
if (!curr.equals(emptyTreeNode)) {
if (curr.left == null) {
queue.offer(emptyTreeNode);
} else {
queue.offer(curr.left);
}
if (curr.right == null) {
queue.offer(emptyTreeNode);
} else {
queue.offer(curr.right);
}
}
rowList.add(curr.val);
--count;
}
if (!checkList(rowList))
return false;
}
return true;
}
判断回文list的方法
/**
* 双指针判断回文list
*
* @param list
* @return
*/
public boolean checkList(ArrayList<Integer> list) {
int l = 0;
int r = list.size() -1;
while (l < r){
if (list.get(l).equals(list.get(r))){
l++;
r--;
}else {
return false;
}
}
return true;
}
复杂度分析
- 时间复杂度：O(n)，二叉树层序遍历的时间复杂度
- 空间复杂度：O(n)，遍历队列所需要的最大空间
方法二
当然这道题目可以换一种思想就是，就是如何有一个一摸一样的二叉树，也就是双树问题
正常的前序遍历是
处理当前节点-> 左子树 -> 右子树
是不是还可以这样处理前节点-> 右子树-> 左子树
同时遍历这两个树 1.按照处理当前节点-> 左子树 -> 右子树 2.按照处理前节点-> 右子树-> 左子树
boolean isSymmetrical(TreeNode pRoot)
{
return judge(pRoot, pRoot);
}
public boolean judge(TreeNode pRoot, TreeNode mirropRoot){
//处理特殊值
if(pRoot == null && mirropRoot == null) return true;
else if(pRoot ==null || mirropRoot == null) return false;
else if(pRoot.val != mirropRoot.val) return false;
boolean isA = judge(pRoot.left, mirropRoot.right);
boolean isB = judge(pRoot.right, mirropRoot.left);
return isA && isB;
}
复杂度分析
- 时间复杂度：O(n)，二叉树层序遍历的时间复杂度
- 空间复杂度：O(n)，遍历队列所需要的最大空间
