精华内容
下载资源
问答
  • 对称二叉树

    2021-07-16 20:41:28
    一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树: 1、二叉树; 2、将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。 下图中节点内的数字为权值,节点外的ididid表示节点...

    这是蒟蒻认真写的第一篇题解,如有欠缺,请理解

    题目描述

    一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:

    1、二叉树;

    2、将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。

    下图中节点内的数字为权值,节点外的 i d id id表示节点编号。

    Alt
    现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数最多。请输出这棵子树的节点数。

    注意:只有树根的树也是对称二叉树。本题中约定,以节点为 T T T子树根的一棵“子树”指的是:节点 T T T和它的全部后代节点构成的二叉树。

    输入格式
    第一行一个正整数 n n n,表示给定的树的节点的数目,规定节点编号 1 ∼ n 1\sim n 1n,其中节点 1 1 1输入格式
    第一行一个正整数,表示给定的树的节点的数目,规定节点编号,其中节点是树根。

    第二行 n n n个正整数,用一个空格分隔,第 i i i个正整数 v [ i ] v[i] v[i]代表节点 i i i的权值。

    接下来 n n n行,每行两个正整数 l [ i ] , r [ i ] l[i],r[i] l[i],r[i],分别表示节点 i i i的左右孩子的编号。如果不存在左 / 右孩子,则以 − 1 -1 1表示。两个数之间用一个空格隔开。是树根。

    第二行个正整数,用一个空格分隔,第个正整数代表节点的权值。

    接下来行,每行两个正整数,分别表示节点的左右孩子的编号。如果不存在左 / 右孩子,则以表示。两个数之间用一个空格隔开。

    样例

    【输入样例 1】

    2
    1 3
    2 -1
    -1 -1

    【输出样例 1】

    1

    【输入样例 2】

    10
    2 2 5 5 5 5 4 4 2 3
    9 10
    -1 -1
    -1 -1
    -1 -1
    -1 -1
    -1 2
    3 4
    5 6
    -1 -1
    7 8

    【输出样例 2】

    3

    数据范围与提示

    【输入输出样例 1 说明】

    Alt
    最大的对称二叉子树为以节点为 2 2 2树根的子树,节点数为 1 1 1

    【输入输出样例2说明】
    Alt
    最大的对称二叉子树为以节点为 7 7 7树根的子树,节点数为 3 3 3

    【数据规模与约定】
    25 25 25个测试点。
    v [ i ] ≤ 1000 v[i] ≤ 1000 v[i]1000
    测试点 1 ∼ 3 1 \sim 3 13, n ≤ 10 n ≤ 10 n10,保证根结点的左子树的所有节点都没有右孩子,根结点的右 子树的所有节点都没有左孩子。
    测试点 4 ∼ 8 4 \sim 8 48, n ≤ 10 n ≤ 10 n10
    测试点 9 ∼ 12 9 \sim 12 912, n ≤ 1 0 5 n ≤ 10^5 n105 ,保证输入是一棵“满二叉树” 。
    测试点 13 ∼ 16 13 \sim 16 1316, n ≤ 1 0 5 n ≤ 10^5 n105,保证输入是一棵“完全二叉树”。
    测试点 17 ∼ 20 17 \sim 20 1720, n ≤ 1 0 5 n ≤ 10^5 n105,保证输入的树的点权均为 11。
    测试点 21 ∼ 25 21 \sim 25 2125, n ≤ 1 0 6 n ≤ 10^6 n106

    本题约定:

    层次:节点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一节 点的层次等于其父亲节点的层次加 1 1 1

    树的深度:树中节点的最大层次称为树的深度。

    满二叉树:设二叉树的深度为 h h h,且二叉树有 2 h − 1 2^h-1 2h1个节点,这就是满二叉树。

    思路

    首先,要把对称二叉树的概念搞清楚,下图有很详细的解释
    Alt
    对称二叉树,权值要对称,然后结构也要对称。

    简单分析一下题面:对称二叉树的最大结点数,最小是 1 1 1,然后可以开始分析数据范围,不难发现输出1,3,6可以水很多分,当然3是最多的,如果是洛谷数据可以水到32分(好像是,不要问我怎么知道的),当然优秀的我们怎么可以水分,即便这是一道NOIP原题。

    初始化存储在此不作赘余,相信刷到这题的树已经有些水准,关于孩子表示法双亲表示法之类的,可以使代码条理化,其实也可开几个数组

    先用一个函数搜索以 i i i为结点的最大对称二叉树,建议记忆化,省时间,又方便了后面的操作,注意如果搜索到节点为 − 1 -1 1则代表已经无路可搜,即为出口,直接返回,接着继续遍历,以它的两个孩子为结点。

    接下来是一个 c h e c k check check函数,用以判断是否成立,现在就要用到 r [ i ] r[i] r[i]了,如果当前结点的只有一个孩子都不相同,直接跳出,若是没有孩子,返回 t r u e true true,如果有两个孩子,继续判断它们的权值(即是 v [ i ] v[i] v[i]),之后,想到对称二叉树的定义,第一个孩子的左孩子与第二个孩子的右孩子进行递归判断,第一个孩子的右孩子与第二个孩子的左孩子进行递归判断

    用一个变量存储答案,寻找结点满足要求的 d p [ i ] dp[i] dp[i]最大值,最后输出, o v e r ! over! over!

    最后总结一下,两个重要函数,缺一不可,第一个函数为第二个函数作铺垫,第二个函数为第一个函数返回值作判断,相辅相成。

    代码时间

    备注:此题题面制作不易,代码也考验思路,请先理解思路,不要直接TJ,珍惜一下作者的劳动成果,感谢您的理解

    #include<bits/stdc++.h>
    using namespace std;
    int n,dp[1000005],ans;
    struct Tree{
    	int v,Lchild,Rchild;
    }a[1000005];
    int dfs(int x){
    	if(x==-1)return 0;
    	if(dp[x]!=0)return dp[x];
    	return dp[x]=dfs(a[x].Lchild)+dfs(a[x].Rchild)+1;
    }
    bool check(int x,int y){
    	int tot=0;
    	if(x==-1)tot++;
    	if(y==-1)tot++;
    	if(tot==1)return false;
    	if(tot==2)return true;
    	if(a[x].v==a[y].v)return(check(a[x].Lchild,a[y].Rchild)&&check(a[y].Lchild,a[x].Rchild));
    	else return false;
    }
    int main(){
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
    	for(int i=1;i<=n;i++)scanf("%d %d",&a[i].Lchild,&a[i].Rchild);
    	dfs(1);
    	for(int i=1;i<=n;i++){
    		if(check(a[i].Lchild,a[i].Rchild)){
    			ans=max(ans,dp[i]);
    		}
    	}
    	printf("%d",ans);
    	return 0;
    }
    
    
    展开全文
  • js代码-(算法)(二叉树)对称二叉树判断
  • Leetcode对称二叉树

    2021-01-19 21:08:36
    给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树[1,2,2,3,4,4,3]是对称的。 但是下面这个[1,2,2,null,3,null,3]则不是镜像对称的: 假设二叉树的节点定义如下所示: public class TreeNode { ...

    题目描述

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

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

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

    假设二叉树的节点定义如下所示:

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode() {
        }
    
        public TreeNode(int val) {
            this.val = val;
        }
    
        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    题解

    其实所谓的镜像对称,就是沿中间画一条竖线,折叠起来值相等,能重合,如下图,相同颜色的节点值相等,是一颗镜像对称的二叉树。

    如下就不是一个镜像对称的二叉树

    递归解法:

    如下图所示,用两种颜色标识左半部分和右半部分,我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,p 指针和 q 指针一开始都指向这棵树的根,随后 p 右移时,q 左移,p 左移时,q 右移。每次检查当前 p 和 q 节点的值是否相等,如果相等再判断左右子树是否对称。


    经过上面分析代码如下

    private static boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }
    
        private static boolean check(TreeNode p, TreeNode q) {
            //说明是对称的
            if (p == null && q == null) {
                return true;
            }
    
            //只要有一个为空,说明不是对称的
            if (p == null || q == null) {
                return false;
            }
            
            //如果两个都不为空,则对应的值必须相等,并且 p 左移[即p.left] 和 q 右移[即q.right] 必须也同步是对称节点,并且 p 右移 和 q 左移也同步是对称节点
            return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
        }

    迭代解法:定义一个辅助队列,定义两个指针 p 和 q分别指向 root ,起始时把 p 和 q入队列

    出栈两个节点

    (1)如果两个节点相等,则同时执行 p 左移 「即p.left」 和 q 右移「即q.right」  入队列, p 右移「即p.right」 和 q 左移「即q.left」入队列

    (2)如果两个节点不相等,则可以直接返回false。

     

     

    经过上面的分析代码如下:

    private static boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }
    
        private static boolean check(TreeNode p, TreeNode q) {
            //定义一个队列
            Queue<TreeNode> queue = new LinkedList<>();
    
            //起始时把两个节点入队列
            queue.offer(p);
            queue.offer(q);
            while (!queue.isEmpty()) {
    
                //出队列两个节点
                p = queue.poll();
                q = queue.poll();
    
                //如果两个节点为空,则继续执行后续操作
                if (p == null && q == null) {
                    continue;
                }
    
                //如果节点不相等,则判定不是对称的,可以直接返回false
                if ((p == null || q == null) || p.val != q.val) {
                    return false;
                }
    
                //则p左移 和 q右移 入队列
                queue.offer(p.left);
                queue.offer(q.right);
    
                //p 右移 和 q 左移 入队列
                queue.offer(p.right);
                queue.offer(q.left);
            }
            return true;
        }
    

     

    展开全文
  • 一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树: 二叉树; 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。 下图中节点内的数字为权值,节点外的 id 表示节点编号。 ...

    题目描述
    一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:

    1. 二叉树;
    2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。

    下图中节点内的数字为权值,节点外的 id 表示节点编号。
    在这里插入图片描述

    现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数 最多。请输出这棵子树的节点数。

    注意:只有树根的树也是对称二叉树。本题中约定,以节点 T为子树根的一棵“子树”指的是:节点T和它的全部后代节点构成的二叉树。

    本题约定: 层次:节点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一节
    点的层次等于其父亲节点的层次加 1。 树的深度:树中节点的最大层次称为树的深度。
    满二叉树:设二叉树的深度为 h,且二叉树有 2h − 1 个节点,这就是满二叉树。
    在这里插入图片描述

    完全二叉树:设二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大
    个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
    在这里插入图片描述

    输入描述:
    第一行一个正整数 𝑛,表示给定的树的节点的数目,规定节点编号 1~n,其中节点1 是树根。
    第二行 𝑛 个正整数,用一个空格分隔,第 𝑖 个正整数 𝑣𝑖 代表节点 𝑖 的权值。
    接下来 𝑛 行,每行两个正整数 𝑙 , 𝑟 ,分别表示节点 𝑖 的左右孩子的编号。如果不存在左 / 右孩子,则以 −1 表示。两个数之间用一个空格隔开。
    输出描述:
    输出文件共一行,包含一个整数,表示给定的树的最大对称二叉子树的节点数。
    示例1
    输入

    2
    1 3
    2 -1
    -1 -1
    

    输出

    1
    

    说明

    最大的对称二叉子树为以节点 2 为树根的子树,节点数为 1。
    示例2
    输入

    10
    2 2 5 5 5 5 4 4 2 3
    9 10
    -1 -1
    -1 -1
    -1 -1
    -1 -1
    -1 2
    3 4
    5 6
    -1 -1
    7 8
    

    输出

    3
    

    解题思路
    数据结构

    struct node
    {
    
        int v;
        int l,r;
    }tree[maxn];
    

    1)用check(l,r)函数来判断左右子树是否一样

    int check(int l,int r)//判断二叉树是否对称
    {
        if(l==r) return 1;
        if(tree[l].v==tree[r].v)
        {   if(check(tree[l].l,tree[r].r)&&check(tree[l].r,tree[r].l))
               return 1;
        }
        return 0;
    
    }
    

    2)dfs函数来统计节点个数

    void  yu(int i)
    {
        int l=tree[i].l;
        int r=tree[i].r;
        if(i==-1) return ;
        sum[i]=1;
        yu(l);yu(r);
        sum[i]+=sum[l]+sum[r];
    }
    

    c++代码

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+10;
    
    int n;
    struct node
    {
    
        int v;
        int l,r;
    }tree[maxn];
    int sum[maxn]={0};
    int count1=0;
    int check(int l,int r)//判断二叉树是否对称
    {
        if(l==r) return 1;
        if(tree[l].v==tree[r].v)
        {
    
            if(check(tree[l].l,tree[r].r)&&check(tree[l].r,tree[r].l))
               return 1;
        }
        return 0;
    
    }
    void  yu(int i)//统计结点数量
    {
        int l=tree[i].l;
        int r=tree[i].r;
        if(i==-1) return ;
        sum[i]=1;
        yu(l);yu(r);
        sum[i]+=sum[l]+sum[r];
    
    
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            cin>>tree[i].v;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>tree[i].l>>tree[i].r;
        }
        yu(1);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
    
            if(check(tree[i].l,tree[i].r)) ans=max(ans,sum[i]);
        }
        cout<<ans<<endl;
        return 0;
    
    }
    
    
    展开全文
  • 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树[1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 进阶: 你...

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

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

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

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

        1
       / \
      2   2
       \   \
       3    3

    进阶:

    你可以运用递归和迭代两种方法解决这个问题吗?
    链接:https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xoxzgv/
    来源:力扣(LeetCode)

    #!/usr/bin/python3
    # -*- coding: utf-8 -*-
    
    # BinaryTree的实现可参考前面文章
    from Tree.BinaryTree import BinaryTree
    
    tree = BinaryTree('root')
    tree.insert_left('001')
    tree.insert_right('001')
    tree.get_left_node().insert_left('--001')
    tree.get_left_node().insert_right('-001')
    tree.get_right_node().insert_left('-001')
    tree.get_right_node().insert_right('--001')
    # tree.get_right_node().get_right_node().insert_right('right-right-002')
    
    
    # 递归判断是否为对称二叉树
    def is_symmetric_recursive(root_node):
        if not root_node:
            return True
    
        def helper(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False
            if left.key == right.key:
                return helper(left.left, right.right) and helper(left.right, right.left)
            return False
        return helper(root_node.leftChild, root_node.rightChild)
    
    
    # 迭代判断是否为对称二叉树
    def is_symmetric_non_recursive(root_node):
        if not root_node:
            return True
        stack = [root_node.leftChild, root_node.rightChild]
        while stack:
            right = stack.pop()
            left = stack.pop()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.key != right.key:
                return False
            stack.extend([left.leftChild, right.rightChild, left.rightChild, right.leftChild])
        return True
    
    
    print(is_symmetric_non_recursive(tree))


     

    展开全文
  • 对称二叉树 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 解题思路 递归求解 两个数互为镜像的条件: 1.他们的两个...
  • 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 说明: 如果...
  • 一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树: 1. 二叉树; 2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。 下图中节点内的数字为权值,节点外的id表示节点编号。 ...
  • 二叉树 对称二叉树

    2019-02-21 23:58:41
    请实现一个函数,用来判断一颗二叉树是不是对称的。 如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。   基本思路:判断左右2颗子树是否对称 判断节点值是否相等 不相等返回false 继续向下判断 左...
  • 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 思路 判断...
  • 对称二叉树 前言: 刚刚参加完csp2020的初赛.....直接崩溃,感觉普及提高都进不了,颓废了来刷刷题,打了半天才打出这道题,心态炸了..... 题目描述: 一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,205
精华内容 9,282
关键字:

对称二叉树