计算机科学基础leetcode刷题二叉树
Source
Edit
History

101. 对称二叉树

Problem: 101. 对称二叉树

思路

image.png

  • 使用后序遍历,这样才能对左右节点进行一个对比

  • 先做一个总体的判断,左右是否不相等,具体为:

    - 只要有一个为空一个不为空

    - 只要两个数值不相等

  • 还有一个情况是两个子节点都为空返回true

  • 再后续遍历

  • bool a=左节点

  • bool b=右节点

  • return a && b

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
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

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),

 * right(right) {}

 * };

 */

class Solution {

public:

    bool isSymmetric(TreeNode* root) {

        return foreach(root->left,root->right);

    }

    bool foreach (TreeNode* left, TreeNode * right) {

        if (left == nullptr && right != nullptr)

            return false;

        else if (left != nullptr && right == nullptr)

            return false;

        else if (left == nullptr && right == nullptr)

            return true;

        else if (left->val != right->val)

            return false;

        int a = foreach (left->left, right->right);

        int b = foreach (right->left, left->right);

        return a && b;

    }

};