題目來源：Same Tree

問題：
給予兩棵二元樹 (Binary Tree), 試著寫一個方法來驗證這兩棵樹是否相等或不相等。

// 題目對於二元樹的定義
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

想法
首先先處理樹為空的狀況(也就是 null), 因為如果不先處理掉 null 的狀況，在後面判斷遇到 null 時可能就會造成 null exception.

//  處理樹為空(null) 的狀況
if (root1 == null && root2 ==null)
    return true;
if ( (root1 == null && root2 != null) || (root1 != null && root2 == null) )
    return false;

接著我們可以利用兩個 Stack 來走訪這兩棵樹，置於怎麼走訪可以選擇 BFS 或 DFS 都行。只要兩棵樹的走訪順序相同即可。

// 將兩棵樹的 root push 進 stack 準備進行兩棵樹的走訪
stack1.Push(root1);
stack2.push(root2);

在這裡，我先將走訪的 終止條件 條件設定成兩個 Stack 其中一個不為空 就繼續比對走訪
首先是將 stack 中的節點 pop 出來進行比對

// c# 終止條件
while (stack1.Count >0 || stack2.Count >0 ) {
    ....
}






//  比對節點
var node1 = stack1.Pop();
var node2 = stack2.Pop();

if (node1.val != node2.val)
    return false;

假設節點相同，接下來就是比對這個節點的子節點是否相對應，也就是說左、右子節點要對應。
假設 node1 有左子節點，而 node2 沒有，或 node1 有右子節點 node2 沒有，這樣就可以直接回傳 false 了，因為子節點沒有對應到。

// 判斷目前節點的子節點是否對稱
if ((node1.left != null && node2.left == null) ||
      (node1.left == null && node2.left != null))
    return false;
else if ( (node1.right == null && node2.right != null) ||
           (node1.right != null && node2.right == null) )
    return false;

如果目前節點相同，目前節點的子節點也對稱。我們就重複以上步驟，繼續比較下一個節點。但再往下一個節點前，記得將目前節的的子節點 push 進 stack 這樣才能繼續往下走訪下去。

將目前節點的子節點 push 進 stack

// 因為在前面已經判斷過子節點是否對稱，所以只要其中之一個節點有**左** 或 **右**節點
// 則另一個節點也會有**左** 或 **右**節點
if (node1.left != null) {
    stack1.Push(node1.left);
    stack2.Push(node2.left);
}
if (node1.right != null) {
    stack1.Push(node1.right);
    stack2.Push(node2.right);
}

最後根據我們的分析，來統整一下：
虛擬碼

Push root1 進 stack1
Push root2 進 stack2
當 （stack1 或 stack2 不為空時) {
    // 判斷有 null 的情況
    若 stack1 和 stack2 都會 null
        回傳 TRUE (相同)
    若 stack1 和 stack2 只有其中一個為 null
        回傳 FALSE (不相同)

    // 比對節點
    stack1 Pop 出一個節點到 節點1
    stack2 Pop 出一個節點到 節點2
    若 節點1 不等於 節點2
        回傳 FALSE (不相同)
    
    // 判斷節點的 子節點 是否對稱
    若節點1和節點2其中之一沒有 左子節點
        回傳 FALSE
    若節點1和節點2其中之一沒 右子節點
        回傳 FALSE

    // 將子節點 Push 進 stack 好繼續走訪下去
    若 節點1 有左子節點
        Push 節點1 的 左子節點 進 Stack1
        Push 節點2 的 左子節點 進 Stack2

    若 節點1 有 右子節點
        Push 節點1 的 右子節點 進 Stack1
        Push 節點2 的 右子節點 進 Stack2
}

// 全比對完後
回傳 TRUE

• 如果你用 C＃ 可以利用我的 測試程式 來驗證
• 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證

我的 C# 版本解法

public bool isSameTree(TreeNode root1, TreeNode root2)
{
    if (root1 == null && root2 == null) return true;
    if ((root1 == null && root2 != null) ||
        (root1 != null && root2 == null))
        return false;

    Stack<TreeNode> stack1 = new Stack<TreeNode>();
    Stack<TreeNode> stack2 = new Stack<TreeNode>();

    stack1.Push(root1);
    stack2.Push(root2);

    while (stack1.Count > 0 || stack2.Count > 0)
    {
        var node1 = stack1.Pop();
        var node2 = stack2.Pop();

        if (node1.val != node2.val)
            return false;

        if ((node1.left != null && node2.left == null) ||
              (node1.left == null && node2.left != null))
            return false;
        else if ( (node1.right == null && node2.right != null) ||
                   (node1.right != null && node2.right == null) )
            return false;

        if (node1.left != null)
        {
            stack1.Push(node1.left);
            stack2.Push(node2.left);
        }

        if (node1.right != null)
        {
            stack1.Push(node1.right);
            stack2.Push(node2.right);
        }
    }

    return true;
}

然後在稍微重構一下，因為在比對子節點是否對稱或兩棵樹是否其中一顆為空時，我原本是用這樣的寫法：

 if ((node1.left != null && node2.left == null) || (node1.left == null && node2.left != null)) 

和

if ((root1 == null && root2 != null) || (root1 != null && root2 == null))

但是有沒有發現，兩者不同要為真很像另一個之前用過的布林運算 XOR 呢？所以我們可以將其改寫成

if (node1.left == null ^ node2.left == null )

和

if (root1 == null ^ root2 == null)

重構之後的程式碼

public bool isSameTree(TreeNode root1, TreeNode root2)
{
    if (root1 == null && root2 == null) return true;
    if (root1 == null ^ root2 == null) return false;

    Stack<TreeNode> stack1 = new Stack<TreeNode>();
    Stack<TreeNode> stack2 = new Stack<TreeNode>();

    stack1.Push(root1);
    stack2.Push(root2);

    while (stack1.Count > 0)
    {
        var node1 = stack1.Pop();
        var node2 = stack2.Pop();

        if (node1.val != node2.val)
            return false;

        bool isOnlyOneNodeHasLeftChild = node1.left == null ^ node2.left == null;
        bool isOnlyOneNodeHasRightChild = node1.right == null ^ node2.right == null;

        if (isOnlyOneNodeHasLeftChild || isOnlyOneNodeHasRightChild)
            return false;

        if (node1.left != null)
        {
            stack1.Push(node1.left);
            stack2.Push(node2.left);
        }

        if (node1.right != null)
        {
            stack1.Push(node1.right);
            stack2.Push(node2.right);
        }
    }

    return true;
}