Justice's Site

相同的树

 滴水穿石  256  2 分钟

相同的树

CategoryDifficultyLikesDislikes
algorithmsEasy (59.91%)753-

Tags

tree | depth-first-search

Companies

bloomberg

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

示例 1：

1
2

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

1
2

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

1
2

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn is_same_tree(
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> bool {
        match (p, q) {
            (None, None) => true,
            (Some(p), Some(q)) => {
                p.borrow().val == q.borrow().val
                    && Solution::is_same_tree(p.borrow().left.clone(), q.borrow().left.clone())
                    && Solution::is_same_tree(p.borrow().right.clone(), q.borrow().right.clone())
            }
            _ => false,
        }
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    /*
    ## 解题思路
    * 解法一：递归法
    * 相同树条件：
    * 1. 两根节点都为空节点，两树相同；
    * 2. 只有一个为空节点，两树不同；
    * 3. 都不为空节点，这两者的左右子树应都为相应的相同树
    */
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return ( p->val == q->val 
            && isSameTree(p->left, q->left)
            && isSameTree(p->right, q->right)
        );
    }
};

相关文章：