精华内容
下载资源
问答
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 复制 {2,1,3} 输出 复制 [true,true] 备注: n≤500000 分析: BST特点:左子值比根节点小,右子值比根节点大 ...

    题目描述
    给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。
    示例1
    输入
    复制
    {2,1,3}
    输出
    复制
    [true,true]
    备注:
    n≤500000

    分析:
    BST特点:左子值比根节点小,右子值比根节点大
    完全二叉树特点:每一层节点按照从左到右的顺序存放,每一层必须放满才可以放下一层,比如下图两种就属于不合法的完全二叉树
    在这里插入图片描述
    基于上述特点,我们可以写出代码:

    import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param root TreeNode类 the root
         * @return bool布尔型一维数组
         */
        int pre = Integer.MIN_VALUE;
        boolean f = false;
        public boolean isSearch(TreeNode root){
            if(root!=null){
                boolean res = isSearch(root.left);//左侧走到头
                if(!res) return false;
                if(root.val<=pre) return false;//从右侧开始判断,如果小于左侧,非法
                pre = root.val;//pre 保存的是左侧节点的值
                return isSearch(root.right);
            }
            return true;
        }
        //递归方式
        public boolean isComplete1(TreeNode root){
            if(root == null) return true;
            if(root.left==null&&root.right==null) return true;
            //左子不为空右子为空的情况只能出现一次,类似于我画的图左边那种情况是不合法的
            if(root.left!=null&&root.right==null){
                if(f) return false;
                f = true;
            }
            //左子为空右子不为空是非法的,我画的图右边
            if(root.left==null&&root.right!=null)return false;
            return isComplete1(root.left)&&isComplete1(root.right);
        }
        //非递归方式
        public boolean isComplete2(TreeNode root){
            if(root == null) return true;
            Queue<TreeNode> q=new LinkedList<>();
            q.add(root);
            TreeNode pre = root;//pre保存的是顺序遍历的前一个节点
            while(!q.isEmpty()){
                int c = q.size();
                for(int i = 0;i < c;i++){
                    TreeNode node = q.poll();
                    //出现了我画的图中的情况
                    if(pre == null&&node!=null) return false;
                    if(node!=null){
                        q.add(node.left);
                        q.add(node.right);                    
                    }
                    pre = node;
                }
            }
            return true;
        }
        public boolean[] judgeIt (TreeNode root) {
            // write code here
            boolean[] ans = new boolean[2];
            ans[0] = isSearch(root);
            ans[1] = isComplete2(root);
            return ans;
        }
    }
    
    展开全文
  • 判断是否是完全二叉树(JAVA)

    千次阅读 2018-11-04 20:00:45
    判断一个树是否属于完全二叉树可以从以下2个条件来判断: -层次遍历二叉树 1 任何一个结点如果右孩子不为空,左孩子却是空,则一定不是完全二叉树 2 当一个结点出现右孩子为空时候,判断该结点的层次遍历后继...

    判断完全二叉树-JAVA

    判断一个树是否属于完全二叉树可以从以下2个条件来判断:

    -层次遍历二叉树

    • 1 任何一个结点如果右孩子不为空,左孩子却是空,则一定不是完全二叉树
    • 2 当一个结点出现右孩子为空时候,判断该结点的层次遍历后继结点是否为叶子节点,如果全部都是叶子节点,则是完全二叉树,如果存在任何一个结点不是叶节点,则一定不是完全二叉树。
    class Tree{
    	int value;
    	Tree left;
    	Tree right;
    	public Tree(int value) {
    		this.value = value;
    	}
    }
    
    public class Code04 {
    	public static boolean isCBT(Tree tree) {
    		if(null == tree) {
    			return false;
    		}
    		Tree leftChild = null;
    		Tree rightChild = null;
    		boolean left = false;
    		Queue<Tree> queue = new LinkedList<Tree>();
    		queue.offer(tree);
    		while(!queue.isEmpty()) {
    			Tree head = queue.poll();
    			leftChild = head.left;
    			rightChild = head.right;
    			if((null != rightChild && null == leftChild) //右孩子不等于空,左孩子等于空  -> false
    					||
    				(left && (null != rightChild || null != leftChild)) //开启叶节点判断标志位时,如果层次遍历中的后继结点不是叶节点 -> false
    					) {
    				return false;
    			}
    			if(null != leftChild) {
    				queue.offer(leftChild);
    			}
    			if(null != rightChild) {
    				queue.offer(rightChild);
    			}else {
    				left = true; 
    			}
    		}
    		
    		return true;
    	}
    
    展开全文
  • 需求:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度... * 细节:根节点如果为空,是否属于异常还是平衡二叉树  * 左右节点的差应该是绝对值  * */ 代码实现: bo

    需求:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。


    分析:

    /*

     * 思路:递归思想,左右子树的深度差不能大于1;
     *
     *
     * 细节:根节点如果为空,是否属于异常还是平衡二叉树
     *            左右节点的差应该是绝对值

     * */


    代码实现:

    bool is_balanced_binary_tree(t_binarytree_node *p_root)
    {
    	if (p_root == NULL)
    		return true;
    
    	int left = depth_of_binary_tree(p_root->left);
    	int right = depth_of_binary_tree(p_root->right);
    
    	if ((left - right > 1) || (right - left > 1))
    		return false;
    
    	return is_balanced_binary_tree(p_root->left) && is_balanced_binary_tree(p_root->right);
    }

    总结:

    知识迁移:将计算二叉树深度的算法应用在此场景

    递归思想


    参考文献:

    http://zhedahht.blog.163.com/blog/static/25411174200732975328975/






    展开全文
  • 属于非线性数据结构的一种,概念也极多,是由结点或顶点和边组成的且不存在着任何环的一种数据结构。没有结点的树称为空树。一棵非空的树包括一个根结点,还很可能有多个附加结点,并且所有结点构成一个多级分层...
    0d2ce2fae5575bfd440b5085311e7381.png

    ID:技术让梦想更伟大

    作者:李肖遥

    树的概念

    什么是树?

    树属于非线性数据结构的一种,概念也极多,是由结点或顶点和边组成的且不存在着任何环的一种数据结构。

    没有结点的树称为空树。一棵非空的树包括一个根结点,还很可能有多个附加结点,并且所有结点构成一个多级分层结构。

    树的定义

    n个节点组成的有限集合。n=0,空树;n>0,1个根节点,m个互不相交的有限集,每个子集为根的子树,如图所示为一颗树:

    960e0924ee8eb613cc7ea75888db89b5.png

    树的基本术语

    • 节点的度:树中某个节点的子树的个数。
    • 树的度:树中各节点的度的最大值。
    • 分支节点:度不为零的节点。
    • 叶子节点:度为零的节点。
    • 路径:i->j;
    • 路径长度:路径经过节点数目减1。
    • 孩子节点:某节点的后继节点;
    • 双亲节点:该节点为其孩子节点的双亲节点(父母节点);
    • 兄弟节点:同一双亲的孩子节点;
    • 子孙节点:某节点所有子树中的节点;
    • 祖先节点:从树节点到该节点的路径上的节点;
    • 节点的层次:根节点为第一层,以此类推;
    • 树的高度:树中节点的最大层次;
    • 有序树:树中节点子树按次序从左向右安排,次序不能改变;
    • 无序树:与有序树相反;
    • 森林:互不相交的树的集合。

    树的性质

    1. 树的节点树为所有节点度数加1(加根节点)。
    2. 度为m的树中第i层最多有m^(i-1)个节点。
    3. 高度为h的m次树至多(m^h-1)/(m-1)个节点。
    4. 具有n个节点的m次树的最小高度为logm( n(m-1) + 1 )向上取整。

    二叉树

    二叉树简介

    二叉树是n(n>=0)个结点的有限集合,每一个结点中最多拥有一个左结点和一个右结点,并且没有多余的结点,如图所示:

    14ca4320c2e74378a074e87cc5081d3e.png

    二叉树

    二叉树的特点

    根据二叉树的定义以及图示分析得出二叉树有以下特点:

    1. 每个结点最多有两颗子树,不存在度大于2的结点。
    2. 左子树和右子树的次序不能任意颠倒。
    3. 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

    二叉树的性质

    二叉树具有以下几种特征

    1. 二叉树第i层上的结点数目最多为2{i-1} (i≥1)。
    2. 深度为k的二叉树至多有(2{k}-1)(k≥1)个结点。
    3. 包含n个结点的二叉树的高度至少为log2 (n+1)。
    4. 在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。

    几种特殊的二叉树

    斜树

    所有的结点都只有左(右)子树的二叉树叫左(右)斜树,统称为斜树,如图所示:

    4aa8509f1d9b5e0575c73fec2be6ed23.png

    斜树

    满二叉树

    在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树,其有以下特点

    1. 叶子只能出现在最下一层,否则就不可能达成平衡。
    2. 非叶子结点的度一定是2。
    3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。
    b6bc4980f3be5a2a0c49f9cfe749d105.png

    满二叉树

    完全二叉树

    一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

    8d7a71b54c35fa90456cccb489996959.png

    完全二叉树

    二叉树的存储

    简介

    以创建一颗二叉树,并实现通过特定的插入顺序和读取顺序达成读取为顺序为例子进行简介。

    结点设计

    一颗二叉树的结点设计一定要有如下内容:

    • 结点元素,data域,用来存储数据;
    • 左孩子结点,left指针,用来指向当前结点的下一层的左边结点;
    • 右孩子结点,right指针,用来指向当前结点的下一层的右边结点;

    除此之外,我们使用一棵树的时候需要建立一颗树根,由这个根,来进行逐步的向下构建,其代码如下:

    ae7df27fb66f453e4dab3df7039e2be8.png

    树的创建

    首先创建一个空的结点进行连接,将这个空的结点中的date域赋予数据,再判断tree中是否是一个空树,如果为空,只需要将整个根指向这一个结点即可,如果不为空,再进行两个判断,判断输入的数据是否大于或者小于当前比对的结点数据,根据其大小进行相应的排列,这样存储进入的数据总是有一定规律的,在输出的时候根据这个规律进行输出即可,其代码可以显示为:

    6aee52c553afcfe40ccd2f4d66191926.png

    遍历,显示树

    代码如下:

    d9e3089e7b5fa208f680a46b3c3f9737.png

    树的遍历之先序遍历二叉树

    遍历简介

    遍历是按照一定的规则性,将数据结构中的所有数据全部依次访问,而二叉树需要通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序。

    • 先序遍历:根左右

    先序遍历:

    先序遍历就是在访问二叉树的结点的时候采用,先根,再左,再右的方式,对于一个最简单的访问而言如下图,先序遍历的访问顺序就是A,B,C

    bb18f2bde3e2d8ec7b762dcd8b8950f3.png

    多个结点相互嵌套构成的二叉树如图所示,在访问遍历一开始的时候,先访问根结点A,次访问左节点B,由于左结点中嵌套了一组结点,因此左节点又作为下一个结点的根结点。

    继续沿着B访问到了D,同样由于D中包含了一组新的结点,D又作为根节点继续访问,就又访问到了E,由于E没有后面的结点了,作为D为根的左结点E访问结束后,访问到F,这一组访问结束之后再回退访问G,那么这一个二叉树的先序遍历访问顺序就是:ABDEFGCH

    844c55991d8868db4f1be2d1a659853e.png

    代码实现

    8d97ad7896356475d760d21cebda7a23.png

    扩展->前缀表达式

    我们日常的运算表达式通常是如下形式,这种成为中缀表达式,也就是运算符在运算数的中间,如图,为常规表达式:(a+b)*c

    其二叉树的表现形式为:

    ada4be2b5cc38cf7bf7771fdaa9e24ce.png

    而前缀表达式的表达方式就是 *+cab ,它的一个特征就是符号迁移,常规的表达式是需要大量的括号表达先后顺序的,而这样的表达式表达形式不需要,更容易让计算机处理。

    我们常规的表达式的计算是中序的,而计算机更方便对前缀表达式这样的方式进行理解,进行这样的转换首先思路要进行转换。

    在代码中我们实现这样的转换一般可以利用栈,熟练书些这样的转换就需要STL的掌握。

    树的遍历之中序遍历二叉树

    简介

    • 中序遍历:左根右

    如下图,就一个最简单的二叉树遍历而言,中序遍历的遍历访问过程是先B再A再C。

    3a003068d9987f2d46f5fa30510a0d93.png

    多个结点构成的如图所示,进行第一次访问的时候,我们在ABC中进行遍历,由左根右的顺序,我们遍历访问到B,B同时又作为BDG的根结点,因此需要继续向下进行遍历。

    此时我们遍历到DEF,这时E属于这一组之中的左结点,因此我们根据根左右的先后顺序得到了最先的遍历效果,EDF。

    这EDF同时作为BDG中的左节点(把EDF看作一个整体)进行回溯,此时的访问的结点顺序为EDFBG。

    同理EDFBG作为ABC的左结点根据左根右的顺序EDFBGAC,左半部分访问完毕接着访问右半部分,我们将^CH(^表示空)看作一组左中右,而C就是由EDFBGAC组合而成,因此最终的遍历顺序为:EDFBGACH

    4bccbfd9aefdae895d03e4498aac12ed.png

    代码实现

    07970afa793907ffd1eb7e3e1a8d059e.png

    中缀表达式(常规算式)

    中缀表达式是一个通用的算术或逻辑公式表示方法。中缀表达式就是我们最常用的表达式形式,也是人最容易理解的表达式形式。

    如图,为常规表达式:(a+b)*c

    其二叉树的表现形式为:

    2c849adcd529a6bd00d28e477c86a11a.png

    由前文可知前缀表达式的表达方式就是 *+cab ,我们常规的表达式的计算是中序的,其表达式就是(a+b)*c。

    我们可以理解为将表达式利用二叉树化,然后通过中序遍历的方式进行提取,如果需要发生组合时,需要我们借助括号的形式表示优先级,这样也有一个弊端,就是当多个嵌套的时候需要的括号较多。

    树的遍历之后序遍历二叉树

    简介

    • 后序遍历:左右根

    后序遍历就是在访问二叉树的结点的时候采用,先左,再右,再根的方式,对于一个最简单的访问而言如图,先访问左节点B,之后访问右结点C,最后访问根节点A,后序遍历的访问顺序就是BCA

    5fe367511e8230242305df2b550535a7.png

    多个结点相互嵌套构成的二叉树如下图所示,在访问遍历一开始的时候,先访问左节点B再访问右结点C最后访问A;

    由于B结点其中也包含了新的结点,在面对处理的结点后还存在有与之相联的结点的时候,需要优先处理其的子结点,这也是“递归”的基本思路;

    因此,由于B属于DG的根结点,相较于B,应该先访问D结点,而又由于D结点属于EF的根结点,就又变成先访问E结点,E属于最末端了,根据后序遍历左右根的访问顺序,依次生成EFDGB作为一个整体;

    接着我们需要访问C,由于C又是^HC之中的根结点,我们先访问这个空结点,又因为其是一个空的结点,我们会跳过,就变成了HC的访问顺序;

    最后在汇总的时候EFDGB作为左节点,HC作为右结点,A作为根结点,完成我们最终的遍历顺序EFDGBHCA。

    02dd8ea70a42657a3cbf2a13eeef5706.png

    代码实现

    7d8cee067f422c7f3dfee363f3d4d18c.png

    后缀表达式

    后缀表达式与前缀表达式不同,前缀表达式采用先序遍历的方式遍历访问我们的公式顺序,常规式则就是中序方式,而后缀表达式采用后续遍历的方式进行访问。

    如图,为常规表达式:(a+b)*c

    其二叉树的表现形式为:

    f47bbc0d054372d0652f5623d27abe61.png

    而后缀表达式的表达方式就是ab+c* ,相较于前缀表达式,后缀表达式则就是将符号进行后移,其在计算机中的读取运算概念也符合栈的思路,因此没有什么特殊的不同。

    想要了解C语言更多知识,点击下方【了解更多】,与志同道合的小伙伴一起学习~

    展开全文
  • 这样,首先判断左子树是否为空,不为空就寻找到树根的左孩子节点,然后寻找该节点是否有右孩子,如果有继续寻找,直到找到属于叶子节点的右孩子,此时,该节点的右子树“指向”当前树的右子树,并将当前左子树变为树...
  • 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *lef
  • 计算给定二叉树的所有左叶子之和。 示例: 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24 ...同时判断左右子节点是否为None,则可以知道是不是左叶子节点。 class S...
  • 思路:判断一棵树是否是平衡二叉树属于简单题,用dfs记录每条路径的长度,比较每个节点的左右子树长度,只要不满足就是false。 但是做到一半我竟然卡住了: public boolean flag = true; public boolean ...
  • Promblem:  给定两个二叉树T1和T2,返回T1的某个子树结构... 然后使用KMP算法进行两个字符串匹配,判断子树串是否属于原树串即可 Code:   1 #pragma once 2 #include <iostream> 3 #include &...
  • 这里与邓老师讲的唯一不同之处在于需要判断节点是否在某一层,把同属于某一层的节点一起输出。 思路就是在循环里每次不是pop一次,而是每次把当前队列(插入之前)pop空。 代码 /** * Definition for a binary tree...
  • 通过null来判断某一层是否遍历完了,此外需要的Queue去维护树,将同属于一层的节点值放到list当中,每遇到一层遍历完了,这个list就放入到最后返回的答案集合中。 另外此题对每一行的打印顺序有要求,这里用的是...
  • 面试常考算法题

    2019-01-08 15:07:10
    算法 1、二叉树的算法 二叉树的递归与非递归遍历 二叉树的层序遍历 按行打印二叉树 之字形打印二叉树 ...二叉树的深度 ...根据二叉树的前中序重建二叉树 ...二叉树的子树 ...二叉树的序列化与反序列化 ...判断是否属于二...
  • 问题描述:给定两个二叉树的根节点判断第二树是否是第一个树的子树,如果是返回1,否则返回0. 分析:这个是百度的一道笔试题目,属于经典的数据结构问题,子树判断问题,针对这个问题可以采用递归的方法判断, ...
  • 一棵树是否为另一棵树的子结构

    千次阅读 2016-06-29 21:45:53
    问题描述:给定两个二叉树的根节点判断第二树是否是第一个树的子树,如果是返回1,否则返回0. 分析:这个是百度的一道笔试题目,属于经典的数据结构问题,子树判断问题,针对这个问题可以采用递归的方法判断, ...
  • 问题描述:给定两个二叉树的根节点判断第二树是否是第一个树的子树,如果是返回1,否则返回0. 分析:这个是百度的一道笔试题目,属于经典的数据结构问题,子树判断问题,针对这个问题可以采用递归的方法判断, ...
  • 并查集通过树形结构实现(不是二叉树奥),通过判断每个元素的根节点是否相同来判断两个元素是否为相同集合。 回到这个题上,题目中有x,y,z三类,是“判断是否属于同一类的问题”,显然考察并查集的相关知识,只不过...
  • 判断两个元素是否属于同一组(通过判断两个元素的根节点是否一样即可) * 2.合并两个元素所在的组(把其中一个元素的根节点的父节点指向另一个元素的根节点) * * 在该实现下,进行一次操作的时间复杂度为O(a(N)) * ...
  • 判断一个树是否是红黑树的条件: ①、根节点必须是黑色节点 ②、节点必须由红色和黑色组成 ③、每一个叶子节点必须是黑色的(null)节点 ④、每一个红色节点的子节点都是黑色,每个黑色节点的子节点没有要求(两个红色...
  • 并查集的使用和优化

    2019-07-25 14:57:00
    并查集  并查集是一个完全二叉树,具体理解就看下面这个题吧:洛谷P1551  可以看到并查集每一个节点都存着其父亲的...这时候只需判断元素是否属于同一集合即可。  要实现并查集,我们可以通过一个结构体和...
  • Union/Find数据结构

    2020-11-08 20:48:33
    并查集 unionfind 基础知识 每一组存储的结构为树结构(不是二叉树), ...1 查询元素是否属于同一组 (method 查找两个元素的根,并判断是否相同 2 合并两组元素 (将一个组的根指向另一个组的根 具体代码 ...
  • 并查集学习笔记

    2015-01-17 14:44:12
    并查集有几个基本操作初始化、查询树的根、合并x,y所属集合、判断x,y是否属于同一集合。 查询是查询树的根节点,两个数的根有共同的根节点,说明两个数属于同一组。 合并就是将一个树的根向另一
  • 碰到二叉树,优先想递归。 这里,后序数组,最后一个是根节点;从数组开始到第一个比root大的元素前面属于左子树;后面属于右子树;可以检查右子树是否都比root大。否,直接返回false;是,递归调用判断函数; ...
  • 补充下,根据书中的代码来看,子结构的定义并不包括叶子节点下的null,也就是说只要B的存在数字的结构存在于A中就行,那么如果B是null树,那么就不属于A的子结构) 书中方法:书上的方法十分清晰,分为两个步骤,先...
  • 3.4.4 判断两棵树是否相等,请实现两棵树是否相等的比较,相等返回1,否则返回其他值,并说明算法复杂度 3.4.5 三个警察和三个囚徒的过河问题 3.4.6 从300万字符串中找到最热门的10条 3.4.7 如何找出字典中的兄弟...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    d. 当输入一个商品时,能显示该商品是否在库存中,如存在库存中,则显示其名称和数量,否则显示“未找到”。 e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数...
  • JAVA面试题最全集

    2010-03-13 13:09:10
    判断一个文件或目录是否存在 如何读写文件 7.Java多态的实现(继承、重载、覆盖) 8.编码转换,怎样实现将GB2312编码的字符串转换为ISO-8859-1编码的字符串。 9.Java中访问数据库的步骤,Statement和...
  • oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 第一章 Oracle入门 一、 数据库概述 数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,它产生于距今五十年前。...
  • 递归体:将root中的数据加入temp,进行累加,判断是否满足sum,递归访问左右子树(撤销选择的细节问题见下方) 剪枝判断:如果cur == sum 且当前节点为叶子节点,则进行存储输出(return的细节问题见下方) ...

空空如也

空空如也

1 2
收藏数 29
精华内容 11
关键字:

判断节点是否属于二叉树