題目

給定兩個二叉樹，編寫一個函數(shù)來檢驗它們是否相同。
如果兩個樹在結構上相同，并且節(jié)點具有相同的值，則認為它們是相同的。

解題思路

這道題的解題思路比較簡單，就是同時遍歷兩顆樹的問題，并比較每個遍歷的結點的值是否相等即可。問題就變成了怎么遍歷，根據(jù)樹型知識
)里描述的，我們有很多種遍歷的方法可以選擇，通過深度優(yōu)先和廣度優(yōu)先都可以，每種優(yōu)先都可以使用遞歸和迭代實現(xiàn)。先看遞歸解決方案

遞歸解法

先找子問題，兩顆樹相同，就是根節(jié)點相同，并且左右子樹也符合這個要求，那么子問題就是每個遍歷到的結點都相同。終止條件就是兩個結點是否相同的條件。我們就可以上述的分解辦法，不斷的迭代這個子問題。

遞歸解法代碼

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //終止條件
        if(p==null && q==null){
            //同時為空，符合要求
            return true;
        }else if(p==null || q==null){
            //不同時為空，說明有不同的結點
            return false;
        }else if(p.val != q.val){
            return false;
        }
        //子問題：如果左右子樹都是相同的樹，那么就是相同的樹
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

迭代解法

對于迭代，我們可以深度優(yōu)先或者廣度優(yōu)先，深度優(yōu)先就是棧，后入先出的數(shù)據(jù)結構，遍歷兩顆樹，比較每一個迭代到的結點?；蛘呤褂脧V度優(yōu)先，層序遍歷兩顆樹，也是比較每一個被遍歷到的結點，方法很多，大家可以每一種都試試，這里只用棧結構的前序遍歷完成解題。先看下怎么使用單個棧完成前序遍歷

如何使用棧實現(xiàn)前序遍歷

image

取出棧頂元素并輸出F (棧結構：空)
然后放入他的右子樹和左子樹(EC)

取出棧頂并輸出C (E)
然后放入他的右子樹和左子樹(ADE)，

....循環(huán)上面的步驟，直到棧為空，就完成了前序遍歷的過程

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //先放入根節(jié)點
        stack.push(root);
        while (!stack.isEmpty()) {
            //執(zhí)行循環(huán)體，先取出棧頂元素并輸出，并依次放入右左結點
            TreeNode node = stack.pop();
            res.add(Integer.valueOf(node.val));
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }

迭代解法代碼

上面給出了使用棧實現(xiàn)前序遍歷的代碼，我們只要同時對兩顆樹進行操作即可，并判斷每一個遍歷到的結點

public boolean isSameTreePre(TreeNode p, TreeNode q) {
        if (p == null && q == null){
            return true;
        }
        if (p == null){
            return false;
        }
        if (q == null){
            return false;
        }
        Stack<TreeNode> stackP = new Stack<>();
        stackP.add(p);
        Stack<TreeNode> stackQ = new Stack<>();
        stackQ.add(q);
        while (!stackP.isEmpty() || !stackQ.isEmpty()) {
            TreeNode pNode = stackP.pop();
            TreeNode qNode = stackQ.pop();
            if (pNode == null && qNode == null) continue;
            if (pNode == null) return false;
            if (qNode == null) return false;
            if (pNode.val != qNode.val) {
                return false;
            } else {
                stackP.add(pNode.right);
                stackQ.add(qNode.right);
                stackP.add(pNode.left);
                stackQ.add(qNode.left);
            }
        }
        return true;
    }