首页 > 代码库 > Leetcode-Symmetric Tree
Leetcode-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 3
But the following is not:
1 / 2 2 \ 3 3
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public boolean isSymmetric(TreeNode root) {12 if (root==null)13 return true;14 15 boolean res = isSymmetricRecur(root.left,root.right);16 17 return res;18 }19 20 //Determine whether the tree "left" and the tree "right" is symmetric.21 public boolean isSymmetricRecur(TreeNode left, TreeNode right){22 //One is null, the other is not, then false;23 if ((left==null && right!=null)||(left!=null&&right==null))24 return false;25 26 //Both are empty, then true;27 if (left==null&&right==null)28 return true;29 30 //Both are not empty, but val is not the same, then false.31 if (left.val!=right.val)32 return false;33 34 //Both of them are leaf nodes35 if (left.left==null&&left.right==null&&right.left==null&&right.right==null)36 if (left.val==right.val)37 return true;38 else 39 return false;40 41 boolean leftSym = isSymmetricRecur(left.left,right.right);42 if (!leftSym)43 return false;44 45 boolean rightSym = isSymmetricRecur(left.right,right.left);46 if (!rightSym)47 return false;48 49 50 return true;51 }52 }
This is an recursion solution. For easy solution, we can use BFS to put every node into a list orderred by level, then check whether the nodes on the same level are symmetric.
NOTE: we need consider all situation carefully. I failed several times because of missing some situations!
Leetcode-Symmetric Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。