C#LeetCode刷题之#100-相同的树（Same Tree）

/ \       / \
2   3   2   3

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

/           \
2             2

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

/ \       / \
2   1    1   2

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

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.

Input:     1         1
/ \       / \
2   3   2   3

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

Output: true

Input:     1         1
/           \
2             2

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

Output: false

Input:     1         1
/ \       / \
2   1   1    2

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

Output: false

```public class Program {

public static void Main(string[] args) {
var p = new TreeNode(1) {
left = new TreeNode(2)
};

var q = new TreeNode(1) {
left = new TreeNode(2)
};

var res = IsSameTree(p, q);
Console.WriteLine(res);

q.right = new TreeNode(6);

res = IsSameTree2(p, q);
Console.WriteLine(res);

}

public static void IsSame(TreeNode p, TreeNode q, ref bool isSameTree) {
//先序遍历分析法
if(p?.val != q?.val) {
isSameTree = false;
return;
}
if(p != null && q != null) {
if(p.left != null || q.left != null) {
IsSame(p.left, q.left, ref isSameTree);
}
if(p.right != null || q.right != null) {
IsSame(p.right, q.right, ref isSameTree);
}
}
return;
}

public static bool IsSameTree(TreeNode p, TreeNode q) {
var isSameTree = true;
IsSame(p, q, ref isSameTree);
return isSameTree;
}

public static bool IsSameTree2(TreeNode p, TreeNode q) {
//优雅递归法
//如果 p 和 q 同时为空，则肯定相
//已经到了递归最底层的调用，也就是递归的最基本情况
//属于递归的终止条件
//以下3行代码均是终止条件
if(p == null && q == null) return true;
//如果 p 为空，q 不为空，则肯定不相同
if(p == null) return false;
//如果 q 为空，p 不为空，则肯定不相同
if(q == null) return false;
//递归调用
return p.val == q.val &&
IsSameTree2(p.left, q.left) &&
IsSameTree2(p.right, q.right);
}

public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}

}
```

```True
False```