LeetCode之Same Tree

【题目】

Same Tree

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.

【代码】

【递归】

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q){
        //同时到达叶子节点,终止
        if(p == NULL && q == NULL){
            return true;
        }
        //不同时到达叶子节点,剪枝
        if(p == NULL || q == NULL){
            return false;
        }
        if(p->val == q->val){
            bool left = isSameTree(p->left,q->left);
            bool right = isSameTree(p->right,q->right);
            return left && right;
        }
        else{
            return false;
        }
    }
};

【迭代】

/*********************************
*   日期：2013-12-08
*   作者：SJF0115
*   题号: 题目: Same Tree
*   来源：http://oj.leetcode.com/problems/same-tree/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q){
        stack
  
    stack;
        stack.push(p);
        stack.push(q);
        //迭代
        while(!stack.empty()){
            //获取节点
            q = stack.top();
            stack.pop();
            p = stack.top();
            stack.pop();
            //终止,q,p都没有左右节点
            if(p == NULL && q == NULL){
                continue;
            }
            //剪枝,有且只有一个没有左右节点,
            if(p == NULL || q == NULL){
                return false;
            }
            //剪枝,节点值不一样
            if(p->val != q->val){
                return false;
            }
            //遍历左右子节点
            stack.push(p->left);
            stack.push(q->left);
            stack.push(p->right);
            stack.push(q->right);
        }
        return true;
    }
};
  

【测试】

/*********************************
*   日期：2013-12-08
*   作者：SJF0115
*   题号: 题目: Same Tree
*   来源：http://oj.leetcode.com/problems/same-tree/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }TreeNode,*BiTree; //按先序序列创建二叉树 int CreateBiTree(BiTree &T){ int data; //按先序次序输入二叉树中结点的值，‘-1’表示空树 scanf("%d",&data); if(data == -1){ T = NULL; } else{ T = (BiTree)malloc(sizeof(TreeNode)); //生成根结点 T->val = data; //构造左子树 CreateBiTree(T->left); //构造右子树 CreateBiTree(T->right); } return 0; } bool isSameTree(TreeNode *p, TreeNode *q){ //同时到达叶子节点,终止 if(p == NULL && q == NULL){ return true; } //不同时到达叶子节点,剪枝 if(p == NULL || q == NULL){ return false; } if(p->val == q->val){ bool left = isSameTree(p->left,q->left); bool right = isSameTree(p->right,q->right); return left && right; } else{ return false; } } int main() { int i,n; BiTree root1,root2= NULL; CreateBiTree(root1); CreateBiTree(root2); printf("%d\n",isSameTree(root1,root2)); return 0; }