题解 | #对称的二叉树#
对称的二叉树
http://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
// 队列层次遍历,双队列判断回文
// java中队列的两种实现:LinkedList可以有null元素,ArrayDeque不可以
// 时空复杂度:O(n)
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
Queue<TreeNode> leftQ = new LinkedList<>();
Queue<TreeNode> rightQ = new LinkedList<>();
leftQ.add(pRoot.left);
rightQ.add(pRoot.right);
while (!leftQ.isEmpty() && !rightQ.isEmpty()){
TreeNode node1 = leftQ.poll();
TreeNode node2 = rightQ.poll();
if (node1 == null && node2 != null)
return false;
if (node1 != null && node2 == null)
return false;
if (node1 == null && node2 == null)
continue;
if (node1.val != node2.val)
return false;
leftQ.add(node1.left);
leftQ.add(node1.right);
rightQ.add(node2.right);
rightQ.add(node2.left);
}
return true;
}
}