JZ58-对称的二叉树
对称的二叉树
https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null) {
return true;
}
return isSame(pRoot.left, pRoot.right);
}
boolean isSame(TreeNode lRoot, TreeNode rRoot) {
if (lRoot == null && rRoot == null) {
return true;
}
if (lRoot == null || rRoot == null) { //只要有任意一个为非空
return false;
}
if (lRoot.val != rRoot.val) {
return false;
}
return isSame(lRoot.left, rRoot.right) && isSame(lRoot.right, rRoot.left);
}
}
/**
* 分享一种非递归算法，主要思路是：设置两个链表，分别代表左子树和右子树。
* 左子树每次都从左往右添加节点，右子树每次都从右往左添加节点。
*/
class Solution2 {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
LinkedList<TreeNode> leftList = new LinkedList<>();
LinkedList<TreeNode> rightList = new LinkedList<>();
leftList.add(pRoot.left);
rightList.add(pRoot.right);
while (!leftList.isEmpty() && !rightList.isEmpty()) {
TreeNode leftNode = leftList.poll();
TreeNode rightNode = rightList.poll();
if (leftNode == null && rightNode == null)
continue;
if (leftNode == null || rightNode == null)
return false;
if (leftNode.val != rightNode.val)
return false;
// 左子树从左往右添加节点
leftList.add(leftNode.left);
leftList.add(leftNode.right);
// 右子树从右往左添加节点
rightList.add(rightNode.right);
rightList.add(rightNode.left);
}
return leftList.isEmpty() && rightList.isEmpty();
}
} 