题解 | 拓扑结构相同子树

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class IdenticalTree {
public:
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // 如果A为空，无法包含任何子树
        if (A == nullptr) {
            return false;
        }
        // 如果B为空，认为是A的子树
        if (B == nullptr) {
            return true;
        }
        
        // 检查当前节点开始的子树是否相同
        if (isSameTree(A, B)) {
            return true;
        }
        
        // 递归检查A的左右子树
        return chkIdentical(A->left, B) || chkIdentical(A->right, B);
    }
    
private:
    bool isSameTree(TreeNode* A, TreeNode* B) {
        // 两个都为空，认为相同
        if (A == nullptr && B == nullptr) {
            return true;
        }
        // 其中一个为空，另一个不为空，不相同
        if (A == nullptr || B == nullptr) {
            return false;
        }
        
        // 检查当前节点值是否相同
        if (A->val != B->val) {
            return false;
        }
        
        // 递归检查左右子树
        return isSameTree(A->left, B->left) && isSameTree(A->right, B->right);
    }
};

public class IdenticalTree {
    public boolean chkIdentical(TreeNode A, TreeNode B) {
        // 如果A为空，无法包含任何子树
        if (A == null) {
            return false;
        }
        // 如果B为空，认为是A的子树
        if (B == null) {
            return true;
        }
        
        // 检查当前节点开始的子树是否相同
        if (isSameTree(A, B)) {
            return true;
        }
        
        // 递归检查A的左右子树
        return chkIdentical(A.left, B) || chkIdentical(A.right, B);
    }
    
    // 判断两棵树是否完全相同
    private boolean isSameTree(TreeNode A, TreeNode B) {
        // 两个都为空，认为相同
        if (A == null && B == null) {
            return true;
        }
        // 其中一个为空，另一个不为空，不相同
        if (A == null || B == null) {
            return false;
        }
        
        // 检查当前节点值是否相同
        if (A.val != B.val) {
            return false;
        }
        
        // 递归检查左右子树
        return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
    }
}

# -*- coding:utf-8 -*-

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

class IdenticalTree:
    def chkIdentical(self, A, B):
        # 如果A为空，无法包含任何子树
        if A is None:
            return False
        # 如果B为空，认为是A的子树
        if B is None:
            return True
        
        # 检查当前节点开始的子树是否相同
        if self.isSameTree(A, B):
            return True
        
        # 递归检查A的左右子树
        return self.chkIdentical(A.left, B) or self.chkIdentical(A.right, B)
    
    def isSameTree(self, A, B):
        # 两个都为空，认为相同
        if A is None and B is None:
            return True
        # 其中一个为空，另一个不为空，不相同
        if A is None or B is None:
            return False
        
        # 检查当前节点值是否相同
        if A.val != B.val:
            return False
        
        # 递归检查左右子树
        return self.isSameTree(A.left, B.left) and self.isSameTree(A.right, B.right)