首页 > 其他 > 详细

101. Symmetric Tree 二叉树是否对称

时间:2017-06-20 00:44:20      阅读:465      评论:0      收藏:0      [点我收藏+]

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   /   2   2
 / \ / 3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   /   2   2
   \      3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * public int val;
  5. * public TreeNode left;
  6. * public TreeNode right;
  7. * public TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11. public bool IsSymmetric(TreeNode root) {
  12. if (root == null) return true;
  13. Queue<TreeNode> queue = new Queue<TreeNode>();
  14. queue.Enqueue(root);
  15. while (queue.Count > 0) {
  16. int count = queue.Count;
  17. List<int?> nextLevel = new List<int?>();
  18. for (int i = 0; i < count; i++) {
  19. TreeNode curNode = queue.Dequeue();
  20. if (curNode.left != null) {
  21. queue.Enqueue(curNode.left);
  22. nextLevel.Add(curNode.left.val);
  23. } else {
  24. nextLevel.Add(null);
  25. }
  26. if (curNode.right != null) {
  27. queue.Enqueue(curNode.right);
  28. nextLevel.Add(curNode.right.val);
  29. } else {
  30. nextLevel.Add(null);
  31. }
  32. }
  33. if (!LevelIsSymmetric(nextLevel)){
  34. return false;
  35. }
  36. }
  37. return true;
  38. }
  39. public bool LevelIsSymmetric(List<int?> list) {
  40. int left = 0;
  41. int right = list.Count - 1;
  42. while (right > left) {
  43. if (list[left++] != list[right--]) {
  44. return false;
  45. }
  46. }
  47. return true;
  48. }
  49. }








101. Symmetric Tree 二叉树是否对称

原文:http://www.cnblogs.com/xiejunzhao/p/74acf933880d0f5f01455f39d66e9a15.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!