本文主要是介绍leetcode刷题101 对称二叉树 Symmetric Tree(简单) Python Java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意:
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1/ \2 2/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1/ \2 2\ \3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
解法一:递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""if not root: # 先判断根节点是否为空return Truereturn self.isMirror(root.left, root.right) # 分成左子树和右子树判断def isMirror(self, p, q): # 判断两棵树是否是镜像树if not p and not q: # 根节点都为空,是return Trueif not p or not q: # 其中有一棵为空,不是return Falsel = self.isMirror(p.left, q.right) # p的左子树和q的右子树是否相同r = self.isMirror(p.right, q.left) # p的右子树和q的左子树是否相同return p.val == q.val and l and r # 值相等,并且p的左=q的右,p的右=q的左
解法二:使用队列
class Solution:def isSymmetric(self, root):"""队列:param root::return:"""if not root:return Truenode_queue = [root.left, root.right] # 在空队列中加入左子树和右子树while node_queue:left = node_queue.pop(0) # 依次弹出两个元素right = node_queue.pop(0)if not right and not left: # 如果均为空,继续下一个循环continueif not right or not left: # 如果只有一个为空,返回Falsereturn Falseif left.val != right.val: # 都非空,再判断值是否相等return Falsenode_queue.append(left.left) # 将两个左右子树的左右子树逆序加入队列node_queue.append(right.right)node_queue.append(left.right)node_queue.append(right.left)#node_queue.extend([left.left, right.right, left.right, right.left]) 或者用这一句话写return True
以下是Java版本:
最简单的思路就是先从左子树然后右子树遍历,记录遍历结果,然后再右子树左子树遍历,记录遍历结果,然后对比
两个遍历结果,看是否相等。
1. public class Solution {
2. public boolean isSymmetric(TreeNode root) {
3. if(root == null)
4. return true;
5. StringBuilder builderOfLeft = new StringBuilder();
6. StringBuilder builderOfRight = new StringBuilder();
7. String traverseLeft = traverseLeft(root,builderOfLeft);
8. String traverseRight = traverseRight(root,builderOfRight);
9. if(traverseLeft.equals(traverseRight)){
10. return true;
11. }
12. return false;
13. }
14. public static String traverseLeft(TreeNode root,StringBuilder builder){
15. if(root == null){
16. builder.append("null");
17. return null;
18. }
19. builder.append(root.val+"");
20. traverseLeft(root.left,builder);
21. traverseLeft(root.right,builder);
22. return builder.toString();
23. }
24. public static String traverseRight(TreeNode root,StringBuilder builder){
25. if(root == null){
26. builder.append("null");
27. return null;
28. }
29. builder.append(root.val+"");
30. traverseRight(root.right,builder);
31. traverseRight(root.left,builder);
32. return builder.toString();
33. }
34. }
用递归:
1. public class Solution {
2. public boolean isSymmetric(TreeNode root) {
3. if (root == null) {
4. return true;
5. }
6. return isSymmetric(root.left, root.right);
7. }
8.
9. public boolean isSymmetric(TreeNode left, TreeNode right) {
10. if (left == null && right == null) {
11. return true;
12. }
13.
14. if (left == null || right == null) {
15. return false;
16. }
17.
18. return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
19. }
20. }
这篇关于leetcode刷题101 对称二叉树 Symmetric Tree(简单) Python Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!