本文共 6223 字，大约阅读时间需要 20 分钟。

一、题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

二、题解

2.1深度递归

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {       public boolean isSameTree(TreeNode p, TreeNode q) {           if(p == null && q == null){               return true;        }        if(p == null || q == null){               return false;        }        else if(p.val != q.val){               return false;        }        else{               return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);        }                  }}

2.2拓展

二叉树系列问题模板：

• 相同的树
• 删除二叉搜索树中的节点
• 二叉搜索树中的插入操作
• 二叉搜索树中的搜索
• 验证二叉搜索树

参考：

参考：

2.2.1二叉树

• 二叉树的节点值加一、判断两颗二叉树是否相等
  

2.2.2BST二叉搜索树

删除操作设计情况较复杂，不在举栗

2.3广度队列、前、中、后单栈、后序双栈解法

 /**     * 递归解法     *     * @param p     * @param q     * @return     */    public boolean isSameTree(TreeNode p, TreeNode q) {           if (p == null && q == null) return true;        if (p == null) return false;        if (q == null) return false;        if (p.val == q.val) {               return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);        } else {               return false;        }    }    /**     * 非递归前序遍历判断相等     * 根左右     *     * @param p     * @param q     * @return     */    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;    }    /**     * 非递归中序遍历判断两棵二叉树是否相等     * 左根右     *     * @param p     * @param q     * @return     */    public boolean isSameTreeMid(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<>();        Stack<TreeNode> stackQ = new Stack<>();        while (p != null || q != null || !stackP.isEmpty() || !stackQ.isEmpty()) {               if (p != null && q != null) {                   stackP.add(p);                stackQ.add(q);                p = p.left;                q = q.left;            } else if (q == null && p == null) {                   p = stackP.pop();                q = stackQ.pop();                if (p.val != q.val) {                       return false;                }                p = p.right;                q = q.right;            } else {                   return false;            }        }        return true;    }    /**     * 二叉树后序遍历判断两颗树相等     * 左右根     * 双栈解法     *     * @param p     * @param q     * @return     */    public boolean isSameTreeEnd1(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<>();        Stack<TreeNode> stackPTmp = new Stack<>();        Stack<TreeNode> stackQ = new Stack<>();        Stack<TreeNode> stackQTmp = new Stack<>();        while (p != null || q != null || !stackPTmp.isEmpty() || !stackQTmp.isEmpty()) {               if (p != null && q != null) {                   stackP.add(p);                stackPTmp.add(p);                stackQ.add(q);                stackQTmp.add(p);                p = p.right;                q = q.right;            } else if (p == null && q == null) {                   p = stackPTmp.pop();                p = p.left;                q = stackQTmp.pop();                q = q.left;            } else {                   return false;            }        }        while (!stackP.isEmpty() && !stackQ.isEmpty()) {               if (stackP.pop().val != stackQ.pop().val) {                   return false;            }        }        return true;    }    /**     * 二叉树后序遍历单栈实现对比判断     *     * @param p     * @param q     * @return     */    public boolean isSameTreeEnd2(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);        TreeNode pPre = null;        Stack<TreeNode> stackQ = new Stack<>();        stackQ.add(q);        TreeNode qPre = null;        while (!stackP.isEmpty() || !stackQ.isEmpty()) {               p = stackP.peek();            q = stackQ.peek();            if (((pPre != null && (p.left == pPre || p.right == pPre)) || (p.left == null && p.right == null)) &&                    ((qPre != null && (q.left == qPre || q.right == qPre)) || (q.left == null && q.right == null))) {                   if (p.val != q.val) {                       return false;                }                pPre = p;                qPre = q;                stackP.pop();                stackQ.pop();            } else {                   if (p.right != null && q.right != null) {                       stackP.add(p.right);                    stackQ.add(q.right);                } else if (p.right != null || q.right != null) {                       return false;                }                if (p.left != null && q.left != null) {                       stackP.add(p.left);                    stackQ.add(q.left);                } else if (p.left != null || q.left != null) {                       return false;                }            }        }        return true;    }