#101. Symmetric Tree

題目要我們確認二元樹是否對稱，最基本的需求是需要檢查每個節點，我們可以用遞迴來處理節點的檢查。
接著由於要比對節點值是否對稱，因此左邊節點的檢查要和右邊節點的檢查同時進行才能比對，同時要滿足對稱的需求，所以在檢查節點的時候，左右的檢查排序會是相反的，也就是說，左邊的子樹的最左邊的葉子，在對稱的情況下會和右邊子樹的最右邊的葉子是一樣的，假定左邊的子樹會先從左節點開始檢查，那麼右邊的子樹就要從右節點開始檢查。

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

複雜度分析：

時間複雜度：由於要檢查每個節點，乍看之下會要執行N次才檢查的完，但是實際上左右是同時進行檢查的，所以最多只會執行N/2次，但時間複雜度的表示仍然是O(N)。
空間複雜度：由於是用遞迴來處理，要等到呼叫堆疊完才會收斂，因此空間複雜度是O(N)。

Follow-up

你可以用遞迴和迭代解決問題嗎？

Iteration

上一個解法已經是遞迴解法了，那這邊要做的是迭代的方式。首先我們會需要建立利用迭代法來檢查節點的架構，利用Stack來儲存節點並且檢查。接下來要注意將節點放入的順序，左子樹和右子樹的順序是相反的，這邊我讓左子樹先往左邊檢查，因此先放右節點再放左節點，右子樹則相反，先放入左節點再放入右節點。

public class Solution { 
	public bool IsSymmetric(TreeNode root) {
        var leftTree = new Stack<TreeNode>();
        var rightTree = new Stack<TreeNode>();
        
        //根結點檢查
        if(root.left==null && root.right==null) return true;
        if((root.left==null && root.right!=null)||
        (root.left!=null && root.right==null)) return false;        

        leftTree.Push(root.left);
        rightTree.Push(root.right);

        while(leftTree.Count!=0 && rightTree.Count!=0){
            var leftTreeNode = (TreeNode) leftTree.Pop();
            var rightTreeNode = (TreeNode) rightTree.Pop();            

            //檢查值是否正確
            if(leftTreeNode.val!=rightTreeNode.val) return false;
            //檢查節點是否相等
            if((leftTreeNode.left==null && rightTreeNode.right!=null)||
            (leftTreeNode.left!=null && rightTreeNode.right==null)) return false;
            if((leftTreeNode.right==null && rightTreeNode.left!=null)||
            (leftTreeNode.right!=null && rightTreeNode.left==null)) return false;

            //將左右節點以相反順序放入Stack
            if(leftTreeNode.right!=null) leftTree.Push(leftTreeNode.right);
            if(leftTreeNode.left!=null) leftTree.Push(leftTreeNode.left);
            
            if(rightTreeNode.left!=null) rightTree.Push(rightTreeNode.left);
            if(rightTreeNode.right!=null) rightTree.Push(rightTreeNode.right);
        }
        return leftTree.Count==0 && rightTree.Count==0;
    }
}

複雜度分析：

時間複雜度：由於要檢查每個節點，乍看之下會要執行N次才檢查的完，但是實際上左右是同時進行檢查的，所以最多只會執行N/2次，但時間複雜度的表示仍然是O(N)。
空間複雜度：存入的節點數量最多會是深度* 左右各一節點* 左右子樹，所以會是Depth* 2 * 2，雖然不多，但還是增加了空間使用，所以時間複雜度為O(N)。

學習重點

遞迴
迭代

#101. Symmetric Tree

題目描述

限制條件

解題思路

Recursion

Follow-up

Iteration

學習重點