Keshawn_lu's Blog

Leetcode 101. 对称二叉树

树 深度优先遍历
字数统计: 248阅读时长: 1 min
2020/05/31 Share

题目简介：

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

思路：

运用递归，由于是镜像对称，所以判定左树的左子树和右树的右子树，左树的右子树和右树的左子树是否相等即可。

tips:

  • 两结点均为空时，相等
  • 只有一结点为空时，不相等

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    bool dfs(TreeNode* left_tree, TreeNode* right_tree){

        if(!left_tree && !right_tree)
            return true;
        if(!left_tree || !right_tree)
            return false;
        
        if(left_tree -> val != right_tree -> val)
            return false;

        return dfs(left_tree -> left, right_tree -> right) 
                && dfs(left_tree -> right, right_tree -> left);
    }

    bool isSymmetric(TreeNode* root) {
        
        return dfs(root, root);
    }
};

最后祝贺自己五月打卡成功！！！

CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网