C++实现LeetCode(101.判断对称树)

[LeetCode] 101.Symmetric Tree 判断对称树

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
/ \
2   2
/ \   / \

3  4 4  3

But the following is not:

    1
/ \
2   2
\   \
3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

判断二叉树是否是平衡树，比如有两个节点n1, n2，我们需要比较n1的左子节点的值和n2的右子节点的值是否相等，同时还要比较n1的右子节点的值和n2的左子结点的值是否相等，以此类推比较完所有的左右两个节点。我们可以用递归和迭代两种方法来实现，写法不同，但是算法核心都一样。

解法一：

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        return isSymmetric(root->left, root->right);
    }
    bool isSymmetric(TreeNode *left, TreeNode *right) {
        if (!left && !right) return true;
        if (left && !right || !left && right || left->val != right->val) return false;
        return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
    }

};

迭代写法需要借助两个队列queue来实现，我们首先判空，如果root为空，直接返回true。否则将root的左右两个子结点分别装入两个队列，然后开始循环，循环条件是两个队列都不为空。在while循环中，我们首先分别将两个队列中的队首元素取出来，如果两个都是空结点，那么直接跳过，因为我们还没有比较完，有可能某个结点没有左子结点，但是右子结点仍然存在，所以这里只能continue。然后再看，如果有一个为空，另一个不为空，那么此时对称性已经被破坏了，不用再比下去了，直接返回false。若两个结点都存在，但是其结点值不同，这也破坏了对称性，返回false。否则的话将node1的左子结点和右子结点排入队列1，注意这里要将node2的右子结点和左子结点排入队列2，注意顺序的对应问题。最后循环结束后直接返回true，这里不必再去check两个队列是否同时为空，因为循环结束后只可能是两个队列均为空的情况，其他情况比如一空一不空的直接在循环内部就返回false了，参见代码如下：

解法二：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q1, q2;
        q1.push(root->left);
        q2.push(root->right);
        while (!q1.empty() && !q2.empty()) {
            TreeNode *node1 = q1.front(); q1.pop();
            TreeNode *node2 = q2.front(); q2.pop();
            if (!node1 && !node2) continue;
            if((node1 && !node2) || (!node1 && node2)) return false;
            if (node1->val != node2->val) return false;
            q1.push(node1->left);
            q1.push(node1->right);
            q2.push(node2->right);
            q2.push(node2->left);
        }
        return true;
    }
};

参考资料：

https://leetcode.com/problems/symmetric-tree/

https://leetcode.com/problems/symmetric-tree/discuss/33054/Recursive-and-non-recursive-solutions-in-Java

到此这篇关于C++实现LeetCode(101.判断对称树)的文章就介绍到这了,更多相关C++实现判断对称树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(241.添加括号的不同方式)

    [LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式 Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Exampl

  • C++实现LeetCode(139.拆分词句)

    [LeetCode] 139. Word Break 拆分词句 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dic

  • C++实现LeetCode(312.打气球游戏)

    [LeetCode] 312. Burst Balloons 打气球游戏 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i]

  • C++实现LeetCode(95.独一无二的二叉搜索树之二)

    [LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

  • C++实现LeetCode(97.交织相错的字符串)

    [LeetCode] 97.Interleaving String 交织相错的字符串 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = &quo

  • C++实现LeetCode(98.验证二叉搜索树)

    [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

  • C++实现LeetCode(96.独一无二的二叉搜索树)

    [LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树 Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1         3  

  • C++实现LeetCode(145.二叉树的后序遍历)

    [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d

  • C++实现LeetCode(99.复原二叉搜索树)

    [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]    1 / 3 \ 2 Output: [3,1,null,null,2]    3 / 1

  • C++实现LeetCode(101.判断对称树)

    [LeetCode] 101.Symmetric Tree 判断对称树 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric:     1 / \ 2   2 / \   / \ 3  4 4  3 But the following is not:     1 / \ 2  

  • C++实现LeetCode(100.判断相同树)

    [LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

  • 使用C语言提取子字符串及判断对称子字符串最大长度

    先来看一个使用C语言从字符串中提取子字符串的基本方法总结: #include <stdio.h> /*处理中文字符*/ /*遍历字符串,非ASCII字符读取2个字节,ASCII读取一个字节,获取字符串长度*/ int StrLenU(const char* string) { int len = 0 ; const char* p = string; while(*p++ != '\0') { if(*p > 0x80 || *p < 0) { p++; } len++; } re

  • C语言详解判断相同树案例分析

    C语言详解判断相同树案例分析

    目录 一.题目描述 二.解题思路 题目难度:简单 一.题目描述 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同. 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的. LeetCode链接:相同的树 二.解题思路 核心思路: 先比较两颗二叉树的根节点 如果「都为空」,则返回 true,说明两树相同. 如果「一个为空一个不为空」,说明这两颗树不相同,则返回 false. 如果「都不为空,但节点值不相同」,说明这两颗树不相同,则返回 false. 经过 1 和

  • C++实现LeetCode(208.实现字典树(前缀树))

    [LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");   // returns true trie.search("app&

  • TypeScript判断对称的二叉树方案详解

    TypeScript判断对称的二叉树方案详解

    目录 前言 实现思路 实现代码 示例代码 前言 如果一颗二叉树和它的镜像一样,那么它就是对称的.实现一个函数用于判断一颗二叉树是否对称,你会怎么做? 本文将分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 实现思路 在上一篇文章二叉树的镜像中我们知道了此问题的解决方案是前序遍历,那么我们可以修改下前序遍历算法,父节点遍历后,先遍历它的右子节点,再遍历它的左子节点,我们把这种算法称为:对称前序遍历 如下图所示的两棵树,我们分别列举下两种遍历的结果: 树A: 前序遍历:8, 6, 5, 7, 6,

  • 用C语言判断一个二叉树是否为另一个的子结构

    1.问题描述: 如何判断一个二叉树是否是另一个的子结构?      比如: 2       /   \      9    8     / \    /    2  3  5   / 6 有个子结构是    9   / \ 2  3 2.分析问题:     有关二叉树的算法问题,一般都可以通过递归来解决.那么写成一个正确的递归程序,首先一定要分析正确递归结束的条件. 拿这道题来讲,什么时候递归结束. <1>第二个二叉树root2为空时,说明root2是第一棵二叉树的root1的子结构,返回tr

  • python机器学习实战之树回归详解

    本文实例为大家分享了树回归的具体代码,供大家参考,具体内容如下 #-*- coding:utf-8 -*- #!/usr/bin/python ''''' 回归树 连续值回归预测 的 回归树 ''' # 测试代码 # import regTrees as RT RT.RtTreeTest() RT.RtTreeTest('ex0.txt') RT.RtTreeTest('ex2.txt') # import regTrees as RT RT.RtTreeTest('ex2.txt',ops=(

  • vue ElementUI实现异步加载树

    本文实例为大家分享了vue ElementUI实现异步加载树的具体代码,供大家参考,具体内容如下 路由文件修改 import List from '@/components/list.vue' import Add from '@/components/add.vue' import Tree from '@/components/tree.vue' import AsynTree from '@/components/asyntree.vue' export default{ routes:[

  • C++ LeetCode1780判断数字是否可以表示成三的幂的和

    目录 LeetCode 1780.判断一个数字是否可以表示成三的幂的和 方法一:二进制枚举 题目分析 解题思路 复杂度分析 AC代码 C++ 方法二:进制转换 AC代码 C++ LeetCode 1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:leetcode.cn/problems/ch… 给你一个整数 n ,如果你可以将 n 表示成若干个不同的三的幂之和,请你返回 true ,否则请返回 false . 对于一个整数 y ,如果存在整数 x 满足 y == 3x ,我们称这个整

随机推荐