Leetcode0100--Same Tree 相同树

【转载请注明】http://www.cnblogs.com/igoslly/p/8707664.html

来看一下题目：

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input: 1 1

/ /

2 3 2 3

[1,2,3], [1,2,3]

Output: true

Example 2:

Input: 1 1

2 2

[1,2], [1,null,2]

Output: false

题目意思：

判断两个二叉树是否相等

注意点：

1、区分左结点和右结点

2、虽然题目给的数组形式，但代码中还是以ListNode* 结点给出

思路：

1、分别遍历树1和树2，结束前若有结点不同，直接返回false

实现方法1：

使用前序遍历方法进行遍历，dfs()子函数递归操作

void dfs(bool * flag,TreeNode *node1,TreeNode * node2){
    if(!(*flag)){return;}   // 判断结果false，无需后续操作，直接返回
    if(node1==NULL&&node2!=NULL){*flag=false;return;}
    if(node1!=NULL&&node2==NULL){*flag=false;return;}   // 若一方为NULL，一方还有值，直接判定false
    if(node1==NULL&&node2==NULL){return;}               // 两方均到根结点、遍历结束
    if(node1->val!=node2->val){*flag=false;return;}     // 当前根结点
    // 遍历左结点和右结点
    dfs(flag,node1->left,node2->left);    
    dfs(flag,node1->right,node2->right);
}
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        bool flag=true;
        dfs(&flag,p,q);
        return flag;
        
    }
};

实现方法2：

简化写法，直接递归原函数isSameTree，首先：① 取消子函数dfs ② 无需分别判断 node1 & node2 的NULL情况

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p&&q)   // p & q 均有值
            return(p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right));
        // return 先判断当前值是否相等
        // 遍历左子树和右子树
        
        else if (p||q)    // p & q 不都有值
            return false;
        else              // p & q 都无值
            return true;
    }
};

扩展：

在某个大神的代码里看到如下几行，是来做为了优化C++流中不断刷新缓冲区，进行：

static int x = [](){ 
    std::ios::sync_with_stdio(false); 
    cin.tie(NULL);  
    return 0; 
}();

具体解释可以看链接：https://www.cnblogs.com/PrayG/p/5749832.html