题目描述

题目：相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点上的值也相同，则认为它们是相同的。

示例 1:

    1         1
   / \       / \
  2   3     2   3

[1,2,3] 和 [1,2,3] 是相同的树。

示例 2:

    1         1
   /           \
  2             2

[1,2] 和 [1,null,2] 不是相同的树。

示例 3:

    1         1
   / \       / \
  2   1     1   2

[1,2,1] 和 [1,1,2] 不是相同的树。

解题思路

为了判断两棵树是否相同，我们可以采用递归的方法。递归的基本思路是：

1. 如果两个节点都为空，则认为它们相同。
2. 如果只有一个节点为空，或者两个节点的值不相等，则认为它们不相同。
3. 如果两个节点都不为空且值相等，则递归地检查它们的左子树和右子树是否也相同。

PHP 示例代码

<?php

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function isSameTree($p, $q) {
    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);
}

// 示例用法
$tree1 = new TreeNode(1);
$tree1->left = new TreeNode(2);
$tree1->right = new TreeNode(3);

$tree2 = new TreeNode(1);
$tree2->left = new TreeNode(2);
$tree2->right = new TreeNode(3);

echo isSameTree($tree1, $tree2) ? "两棵树相同" : "两棵树不相同";

?>

Python 示例代码

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

def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

# 示例用法
tree1 = TreeNode(1)
tree1.left = TreeNode(2)
tree1.right = TreeNode(3)

tree2 = TreeNode(1)
tree2.left = TreeNode(2)
tree2.right = TreeNode(3)

print("两棵树相同" if isSameTree(tree1, tree2) else "两棵树不相同")

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function isSameTree(p, q) {
    if (!p && !q) {
        return true;
    }
    if (!p || !q || p.val !== q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

// 示例用法
let tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);

let tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);

console.log(isSameTree(tree1, tree2) ? "两棵树相同" : "两棵树不相同");

这些示例代码都展示了如何使用递归方法来判断两棵二叉树是否相同。希望这能帮助你理解这个问题，并在面试中给出优秀的答案。同时，也欢迎访问码小课网站了解更多算法和编程技巧。