com-tree

以下是使用 Golang、TypeScript 和 Python 实现二叉树比较（判断两棵二叉树是否相同）的代码。

1. Python 实现

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

def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
    # 递归终止条件：两节点都为空，则相同
    if not p and not q:
        return True
    # 其中一个为空，或值不相等，则不同
    if not p or not q or p.val != q.val:
        return False
    # 递归比较左右子树
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

# 示例
if __name__ == "__main__":
    # 构建两棵相同的树
    tree1 = TreeNode(1, TreeNode(2), TreeNode(3))
    tree2 = TreeNode(1, TreeNode(2), TreeNode(3))
    print(is_same_tree(tree1, tree2))  # True

    # 构建不同的树
    tree3 = TreeNode(1, TreeNode(2), None)
    tree4 = TreeNode(1, None, TreeNode(2))
    print(is_same_tree(tree3, tree4))  # False

2. TypeScript 实现

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0, left: TreeNode = null, right: TreeNode = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    // 两节点均为空
    if (p === null && q === null) return true;
    // 其中一个为空，或值不同
    if (p === null || q === null || p.val !== q.val) return false;
    // 递归比较左右子树
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

// 示例
const tree1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
const tree2 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(isSameTree(tree1, tree2)); // true

const tree3 = new TreeNode(1, new TreeNode(2), null);
const tree4 = new TreeNode(1, null, new TreeNode(2));
console.log(isSameTree(tree3, tree4)); // false

3. Golang 实现

package main

import "fmt"

// TreeNode 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// IsSameTree 判断两棵二叉树是否相同
func IsSameTree(p *TreeNode, q *TreeNode) bool {
    // 两个节点都为空
    if p == nil && q == nil {
        return true
    }
    // 其中一个为空，或值不相等
    if p == nil || q == nil || p.Val != q.Val {
        return false
    }
    // 递归比较左右子树
    return IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right)
}

func main() {
    // 构建两棵相同的树
    tree1 := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}
    tree2 := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}
    fmt.Println(IsSameTree(tree1, tree2)) // true

    // 构建不同的树
    tree3 := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: nil}
    tree4 := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2}}
    fmt.Println(IsSameTree(tree3, tree4)) // false
}

核心思路

• 递归：同时遍历两棵树的对应节点。
• 终止条件：
  • 两个节点均为 nil → 相同。
  • 其中一个为 nil 或节点值不相等 → 不相同。
• 递归步骤：左右子树必须同时相同。

以上三种语言的实现均遵循相同的逻辑，可直接运行测试。