# 100. Same Tree

題目：<https://leetcode.com/problems/same-tree/>

解法一：DFS

Python3：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def listToTree(arr):
    nodes = [TreeNode(arr[0])]
    i = 0
    j = 1
    length = len(arr)
    while j < length:
        if arr[j] is not None:
            tmp = TreeNode(arr[j])
            nodes[i].left = tmp
            nodes.append(tmp)
        j += 1
        if j >= length:
            break
        if arr[j] is not None:
            tmp = TreeNode(arr[j])
            nodes[i].right = tmp
            nodes.append(tmp)
        j += 1
        i += 1
    return nodes[0]

def treeToList(root):
    if not root:
        return []
    from collections import deque
    nodes = deque()
    nodes.append(root)
    arr = []
    arr.append(root.val)
    while len(nodes):
        node = nodes.popleft()
        if node.left:
            nodes.append(node.left)
            arr.append(node.left.val)
        else:
            arr.append(None)
        if node.right:
            nodes.append(node.right)
            arr.append(node.right.val)
        else:
            arr.append(None)
    return arr

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) \
                and self.isSameTree(p.left, q.left)
        

if __name__ == '__main__':
    arr = [1, 2, 3]
    p = listToTree(arr)
    print(treeToList(p))
    
    arr = [1, 2, 3]
    q = listToTree(arr)
    print(treeToList(q))

    ans = Solution().isSameTree(p, q)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* strToTree(char *str) {
    char *token = strtok(str, ",");
    struct TreeNode **nodes = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    nodes[0] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    nodes[0]->val = atoi(token);
    nodes[0]->left = NULL;
    nodes[0]->right = NULL;
    int i = 0, len = 1;
    token = strtok(NULL, ",");
    while (token != NULL) {
        if (strcmp(token, "null") != 0) {
            len++;
            nodes = (struct TreeNode**)realloc(nodes, sizeof(struct TreeNode*) * len);
            nodes[len - 1] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            nodes[len - 1]->val = atoi(token);
            nodes[len - 1]->left = NULL;
            nodes[len - 1]->right = NULL;
            nodes[i]->left = nodes[len - 1];
        }
        token = strtok(NULL, ",");
        if (token == NULL)
            break;
        if (strcmp(token, "null") != 0) {
            len++;
            nodes = (struct TreeNode**)realloc(nodes, sizeof(struct TreeNode*) * len);
            nodes[len - 1] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            nodes[len - 1]->val = atoi(token);
            nodes[len - 1]->left = NULL;
            nodes[len - 1]->right = NULL;
            nodes[i]->right = nodes[len - 1];
        }
        token = strtok(NULL, ",");
        i++;
    }
    return nodes[0];
}

void printLevelOrderWithNull(struct TreeNode* root) {
    struct TreeNode * bfs[10000] = {};
    bfs[0] = root;
    int i = 0, len = 1;
    printf("%d ", root->val);
    while (i < len) {
        if (bfs[i]->left != NULL) {
            bfs[len++] = bfs[i]->left;
            printf("%d ", bfs[i]->left->val);
        } else
            printf("null ");
        if (bfs[i]->right != NULL) {
            bfs[len++] = bfs[i]->right;
            printf("%d ", bfs[i]->right->val);
        } else
            printf("null ");
        i++;
    }
    printf("\n");
}

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
        return true;
    if (p == NULL || q == NULL)
        return false;
    if (p->val != q->val)
        return false;
    return isSameTree(p->right, q->right)
            && isSameTree(p->left, q->left);
}

int main()
{
    char input1[] = "1,2,3";
    struct TreeNode* p = strToTree(input1);
    printLevelOrderWithNull(p);
    printf("\n");
    
    char input2[] = "1,3";
    struct TreeNode* q = strToTree(input2);
    printLevelOrderWithNull(q);
    printf("\n");
    
    bool ans = isSameTree(p, q);
    printf("%s\n", ans ? "True" : "False");
    return 0;
}

解法二：BFS

Python3：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def listToTree(arr):
    nodes = [TreeNode(arr[0])]
    i = 0
    j = 1
    length = len(arr)
    while j < length:
        if arr[j] is not None:
            tmp = TreeNode(arr[j])
            nodes[i].left = tmp
            nodes.append(tmp)
        j += 1
        if j >= length:
            break
        if arr[j] is not None:
            tmp = TreeNode(arr[j])
            nodes[i].right = tmp
            nodes.append(tmp)
        j += 1
        i += 1
    return nodes[0]

def treeToList(root):
    if not root:
        return []
    from collections import deque
    nodes = deque()
    nodes.append(root)
    arr = []
    arr.append(root.val)
    while len(nodes):
        node = nodes.popleft()
        if node.left:
            nodes.append(node.left)
            arr.append(node.left.val)
        else:
            arr.append(None)
        if node.right:
            nodes.append(node.right)
            arr.append(node.right.val)
        else:
            arr.append(None)
    return arr

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        from collections import deque
        bfs = deque()
        bfs.append((p, q))
        while bfs:
            p, q = bfs.popleft()
            if not p and not q:
                continue
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            bfs.append((p.left, q.left))
            bfs.append((p.right, q.right))
        return True

if __name__ == '__main__':
    arr = [1, 2, 3]
    p = listToTree(arr)
    print(treeToList(p))
    
    arr = [1, 2, 3]
    q = listToTree(arr)
    print(treeToList(q))

    ans = Solution().isSameTree(p, q)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* strToTree(char *str) {
    char *token = strtok(str, ",");
    struct TreeNode **nodes = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    nodes[0] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    nodes[0]->val = atoi(token);
    nodes[0]->left = NULL;
    nodes[0]->right = NULL;
    int i = 0, len = 1;
    token = strtok(NULL, ",");
    while (token != NULL) {
        if (strcmp(token, "null") != 0) {
            len++;
            nodes = (struct TreeNode**)realloc(nodes, sizeof(struct TreeNode*) * len);
            nodes[len - 1] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            nodes[len - 1]->val = atoi(token);
            nodes[len - 1]->left = NULL;
            nodes[len - 1]->right = NULL;
            nodes[i]->left = nodes[len - 1];
        }
        token = strtok(NULL, ",");
        if (token == NULL)
            break;
        if (strcmp(token, "null") != 0) {
            len++;
            nodes = (struct TreeNode**)realloc(nodes, sizeof(struct TreeNode*) * len);
            nodes[len - 1] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            nodes[len - 1]->val = atoi(token);
            nodes[len - 1]->left = NULL;
            nodes[len - 1]->right = NULL;
            nodes[i]->right = nodes[len - 1];
        }
        token = strtok(NULL, ",");
        i++;
    }
    return nodes[0];
}

void printLevelOrderWithNull(struct TreeNode* root) {
    struct TreeNode * bfs[10000] = {};
    bfs[0] = root;
    int i = 0, len = 1;
    printf("%d ", root->val);
    while (i < len) {
        if (bfs[i]->left != NULL) {
            bfs[len++] = bfs[i]->left;
            printf("%d ", bfs[i]->left->val);
        } else
            printf("null ");
        if (bfs[i]->right != NULL) {
            bfs[len++] = bfs[i]->right;
            printf("%d ", bfs[i]->right->val);
        } else
            printf("null ");
        i++;
    }
    printf("\n");
}

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode * bfs[1000][2] = {};
    bfs[0][0] = p;
    bfs[0][1] = q;
    int idx = 0, len = 1;
    while (idx < len) {
        if (bfs[idx][0] == NULL && bfs[idx][1] == NULL) {
            idx++;
            continue;
        }
        if (bfs[idx][0] == NULL || bfs[idx][1] == NULL)
            return false;
        if (bfs[idx][0]->val != bfs[idx][1]->val)
            return false;
        bfs[len][0] = bfs[idx][0]->right;
        bfs[len][1] = bfs[idx][1]->right;
        len++;
        bfs[len][0] = bfs[idx][0]->left;
        bfs[len][1] = bfs[idx][1]->left;
        len++;
        idx++;
    }
    return true;
}

int main()
{
    char input1[] = "1,2,3";
    struct TreeNode* p = strToTree(input1);
    printLevelOrderWithNull(p);
    printf("\n");
    
    char input2[] = "1,2,3";
    struct TreeNode* q = strToTree(input2);
    printLevelOrderWithNull(q);
    printf("\n");
    
    bool ans = isSameTree(p, q);
    printf("%s\n", ans ? "True" : "False");
    return 0;
}

###### tags: `leetcode` `breadth-first search` `depth-first search` `binary tree`