摘要：遞歸法復雜度時間空間遞歸棧空間思路如果兩個根節點一個為空，一個不為空，或者兩個根節點值不同，說明出現了不一樣的地方，返回假。代碼遞歸法復雜度時間空間遞歸棧空間思路其實和寫法是一樣的，是比較兩個節點的兩個左邊，然后再比較兩個節點的兩個右邊。

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

時間 O(N) 空間 O(h) 遞歸棧空間

如果兩個根節點一個為空，一個不為空，或者兩個根節點值不同，說明出現了不一樣的地方，返回假。如果兩個節點都是空，則是一樣的，返回真。然后我們再遞歸它們的左右節點，如果遞歸結果中一個或兩個是假，就返回假。否則，說明左右子樹都是完全一樣的。

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

2018/2

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

2018/10

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p != nil && q != nil {
        return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
    }
    return false
}

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

時間 O(N) 空間 O(h) 遞歸棧空間

其實和Same Tree寫法是一樣的，Same Tree是比較兩個節點的兩個左邊，然后再比較兩個節點的兩個右邊。而對稱樹是要判斷左節點的左節點和右節點的右節點相同（外側），左節點的右節點和右節點的左節點相同（內側）。不過對稱樹是判斷一棵樹，我們要用Same Tree一樣的寫法，就要另寫一個可以比較兩個節點的函數。

注意，Leetcode中當根節點為空時，樹也是對稱的

    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root == null ? true : helper(root.left, root.right);
        }
        
        private boolean helper(TreeNode node1, TreeNode node2){
            if(node1 == null && node2 == null){
                return true;
            }
            if(node1 == null || node2 == null || node1.val != node2.val){
                return false;
            }
            return helper(node1.left, node2.right) && helper(node1.right, node2.left);
        }
    }

2018/2

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return root is None or self.helper(root.left, root.right)
        
    def helper(self, node1, node2):
        if node1 is None and node2 is None:
            return True
        if node1 is None or node2 is None:
            return False
        return node1.val == node2.val and self.helper(node1.right, node2.left) and self.helper(node1.left, node2.right)

時間 O(N) 空間 O(h)

因為該題本質就是二叉樹遍歷，所以我們也可以用迭代來解。這里用一個隊列，兩棵樹按照對稱的順序加入節點，然后進行比較。

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Queue queue1 = new LinkedList();
        Queue queue2 = new LinkedList();
        queue1.offer(root.left);
        queue2.offer(root.right);
        while(!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            // 如果都是null，說明是相同的
            if(node1 == null && node2 == null){
                continue;
            }
            // 如果有一個是null，或者值不同，則有問題
            if(node1 == null || node2 == null || node1.val != node2.val){
                return false;
            }
            queue1.offer(node1.left);
            queue2.offer(node2.right);
            queue1.offer(node1.right);
            queue2.offer(node2.left);
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

2018/2

from collections import deque

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        queue1 = deque()
        queue2 = deque()
        queue1.append(root.left)
        queue2.append(root.right)
        while queue1 and queue2:
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            queue1.append(node1.left)
            queue2.append(node2.right)
            queue1.append(node1.right)
            queue2.append(node2.left)
        return True