首页 > 代码库 > Symmetric Tree
Symmetric Tree
题目
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / 2 2 / \ / 3 4 4 3But the following is not:
1 / 2 2 \ 3 3Note:
Bonus points if you could solve it both recursively and iteratively.
方法一
根据层次遍历的思想.首先初始化队列,使用根节点的左右节点。每次取出来两个元素,进行判断。然后,放入两对元素,leftNode.left和rightNode.right 以及 leftNode.right 和 rightNode.left.public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } if (root.left == null && root.right == null) { return true; } if (root.left == null || root.right == null) { return false; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root.left); queue.offer(root.right); while(!queue.isEmpty()) { int len = queue.size()/2; for (int i = 0; i < len; i++) { TreeNode leftNode = queue.poll(); TreeNode rightNode = queue.poll(); if (leftNode.val == rightNode.val) { if (!(leftNode.left == null && rightNode.right == null)) { if (leftNode.left == null || rightNode.right == null) { return false; } else { queue.offer(leftNode.left); queue.offer(rightNode.right); } } if (!(leftNode.right == null && rightNode.left == null)) { if (leftNode.right == null || rightNode.left == null) { return false; } else { queue.offer(leftNode.right); queue.offer(rightNode.left); } } } else { return false; } } } return true; }
方法二
使用递归。private boolean sym(TreeNode leftNode, TreeNode rightNode) { if (leftNode == null && rightNode == null) { return true; } if (leftNode == null || rightNode == null) { return false; } if (leftNode.val == rightNode.val) { return sym(leftNode.left, rightNode.right) && sym(leftNode.right, rightNode.left); } else { return false; } } public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return sym(root.left, root.right); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。