[LeetCode]100.Same Tree

Same Tree

 Total Accepted: 4943 Total Submissions: 11464My Submissions

/**
 * 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
*   題目: 100.Same Tree
*   來源：https://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<TreeNode *> 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
*   題目: 100.Same Tree
*   來源：https://oj.leetcode.com/problems/same-tree/
*   結果：AC
*   來源：LeetCode
*   總結：
**********************************/
#include <iostream>
#include <malloc.h>
#include <queue>
#include <stdio.h>
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;
}