摘要：遞歸法復(fù)雜度時(shí)間空間遞歸?？臻g思路如果兩個(gè)根節(jié)點(diǎn)一個(gè)為空，一個(gè)不為空，或者兩個(gè)根節(jié)點(diǎn)值不同，說明出現(xiàn)了不一樣的地方，返回假。代碼遞歸法復(fù)雜度時(shí)間空間遞歸?？臻g思路其實(shí)和寫法是一樣的，是比較兩個(gè)節(jié)點(diǎn)的兩個(gè)左邊，然后再比較兩個(gè)節(jié)點(diǎn)的兩個(gè)右邊。

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.

時(shí)間 O(N) 空間 O(h) 遞歸?？臻g

如果兩個(gè)根節(jié)點(diǎn)一個(gè)為空，一個(gè)不為空，或者兩個(gè)根節(jié)點(diǎn)值不同，說明出現(xiàn)了不一樣的地方，返回假。如果兩個(gè)節(jié)點(diǎn)都是空，則是一樣的，返回真。然后我們?cè)龠f歸它們的左右節(jié)點(diǎn)，如果遞歸結(jié)果中一個(gè)或兩個(gè)是假，就返回假。否則，說明左右子樹都是完全一樣的。

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

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

其實(shí)和Same Tree寫法是一樣的，Same Tree是比較兩個(gè)節(jié)點(diǎn)的兩個(gè)左邊，然后再比較兩個(gè)節(jié)點(diǎn)的兩個(gè)右邊。而對(duì)稱樹是要判斷左節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)的右節(jié)點(diǎn)相同（外側(cè)），左節(jié)點(diǎn)的右節(jié)點(diǎn)和右節(jié)點(diǎn)的左節(jié)點(diǎn)相同（內(nèi)側(cè)）。不過對(duì)稱樹是判斷一棵樹，我們要用Same Tree一樣的寫法，就要另寫一個(gè)可以比較兩個(gè)節(jié)點(diǎn)的函數(shù)。

注意，Leetcode中當(dāng)根節(jié)點(diǎn)為空時(shí)，樹也是對(duì)稱的

    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)

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

因?yàn)樵擃}本質(zhì)就是二叉樹遍歷，所以我們也可以用迭代來解。這里用一個(gè)隊(duì)列，兩棵樹按照對(duì)稱的順序加入節(jié)點(diǎn)，然后進(jìn)行比較。

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;
            }
            // 如果有一個(gè)是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