【力扣-二叉树】9、相同的树（100） 100 相同的树

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

100. 相同的树

题目描述

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

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

示例 1：

1
2
css复制代码输入： p = [1,2,3], q = [1,2,3]
输出： true

示例 2：

1
2
css复制代码输入： p = [1,2], q = [1,null,2]
输出： false

示例 3：

1
2
css复制代码输入： p = [1,2,1], q = [1,1,2]
输出： false

解析

  • 递归法
    • 确定递归函数的参数与返回值
      • bool traversal(TreeNode *P,TreeNode *q)
    • 确定终止递归的条件
      • 两个节点非空且值相等才进行递归
    • 确定单层递归的逻辑
      • 判断两个节点的值是否相等
  • 迭代法
    • 思路相同

递归法

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
c++复制代码// 递归法
class Solution
{
public:
    bool isSameTree(TreeNode *p, TreeNode *q)
    {
        return traversal(p, q);
    }

    bool traversal(TreeNode *p, TreeNode *q)
    {
        // 如果两个节点都为空，则返回true
        if (p == NULL && q == NULL)
        {
            return true;
        }

        // 两个节点都非空
        if (p != NULL && q != NULL)
        {
            // 判断值是否相等
            // 相等则进行下一层递归
            if (p->val == q->val)
            {
                bool left = same(p->left, q->left);
                bool right = same(p->right, q->right);
                if (left && right)
                {
                    return true;
                }
            }
        }

        return false;
    }
};

迭代法

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
c++复制代码// 迭代法
// 前序遍历
class Solution1
{
public:
    bool isSameTree(TreeNode *p, TreeNode *q)
    {
        if (p == NULL && q == NULL)
        {
            return true;
        }
        stack<TreeNode *> *p_st;
        stack<TreeNode *> *q_st;

        p_st.push(p);
        q_st.push(q);

        // 迭代遍历
        while (!p_st.empty() && !q_st.empty())
        {
            int pSize = p_st.size();
            int qSize = q_st.size();
            // 两个栈的大小不同，则两个树就不同
            if (pSize != qSize)
            {
                return false;
            }

            for (int i = 0; i < pSize; i++)
            {
                TreeNode *pNode = p_st.top();
                p_st.pop();
                TreeNode *qNode = q_st.top();
                q_st.pop();

                // 两个树的节点都为空
                if (pNode == NULL && qNode == NULL)
                {
                    continue;
                }

                // 两个树的结点都非空
                if (pNode != NULL && qNode != NULL)
                {
                    if (pNode->val == qNode->val)
                    {
                        p_st.push(pNode->left);
                        p_st.push(pNode->right);

                        q_st.push(qNode->left);
                        q_st.push(qNode->right);

                        continue;
                    }
                }
                // 不满足上面的两个条件则返回false
                return false;
            }
        }
        // 遍历结束，返回true
        return true;
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%