Symmetric Tree

描述

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.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3

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

  1.     1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3

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

分析

无

递归版

  1. // Symmetric Tree
  2. // 递归版，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public boolean isSymmetric(TreeNode root) {
  5.         if (root == null) return true;
  6.         return isSymmetric(root.left, root.right);
  7.     }
  8.     private static boolean isSymmetric(TreeNode p, TreeNode q) {
  9.         if (p == null && q == null) return true;   // 终止条件
  10.         if (p == null || q == null) return false;  // 终止条件
  11.         return p.val == q.val      // 三方合并
  12.                 && isSymmetric(p.left, q.right)
  13.                 && isSymmetric(p.right, q.left);
  14.     }
  15. }

迭代版

  1. // Symmetric Tree
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public boolean isSymmetric (TreeNode root) {
  5.         if (root == null) return true;
  7.         Stack<TreeNode> s = new Stack<>();
  8.         s.push(root.left);
  9.         s.push(root.right);
  11.         while (!s.isEmpty()) {
  12.             TreeNode p = s.pop ();
  13.             TreeNode q = s.pop ();
  15.             if (p == null && q == null) continue;
  16.             if (p == null || q == null) return false;
  17.             if (p.val != q.val) return false;
  19.             s.push(p.left);
  20.             s.push(q.right);
  22.             s.push(p.right);
  23.             s.push(q.left);
  24.         }
  26.         return true;
  27.     }
  28. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/symmetric-tree.html