精华内容
下载资源
问答
  • 搜索二叉树:中序遍历为升序 任意一个节点的值一定大于该节点左子树中的任意一个节点的值,同时满足该节点的值小于其右子树中的任意一个节点的值(解决效率问题) 方法:非递归版本二叉树中序遍历,把打印过程改成...

    搜索二叉树:中序遍历为升序
    任意一个节点的值一定大于该节点左子树中的任意一个节点的值,同时满足该节点的值小于其右子树中的任意一个节点的值(解决效率问题)
    方法:非递归版本二叉树中序遍历,把打印过程改成判断。

    #include<iostream>
    #include<stack>
    #include<limits.h>
    
    using namespace std;
    
    struct node{
        int value;
        node* left;
        node* right;
        node(int value):
            value(value), left(NULL),right(NULL) {}
    };
    
    bool isBST(node* head){
        if (head == NULL){
            return true;
        }
        stack<node*>newstack;
        int pre = INT_MIN;
        while (!newstack.empty() || head != NULL){
            if (head != NULL){
                newstack.push(head);
                head = head->left;
            }
            else{
                head = newstack.top();
                //cout << head->value << ",";
                if (pre < head->value){
                    pre = head->value;
                }else{
                    return false;
                }
                newstack.pop();
                head = head->right;
            }
        }
        return true;
    }
    
    int main(){
        node* head = new node(4);
        head->left = new node(2);
        head -> right = new node(6);
        head->left->left = new node(1);
        head->left->right = new node(3);
        head->right->left = new node(5);
        head->right->right = new node(7);
        cout << isBST(head) << endl;
    }
    
    
    

    完全二叉树:
    思路:
    1)如果有右孩子,没有左孩子,那肯定不是完全二叉树
    2)当第一次发现左右两个孩子不是双全的时候,后面遍历到的节点全部都是叶节点,否则返回false

    #include<iostream>
    #include<queue>
    using namespace std;
    
    struct node{
        int value;
        node* left;
        node* right;
        node(int value):
            value(value), left(NULL),right(NULL) {}
    };
    
    bool isCST(node* head){
        if(head == NULL){
            return true;
        }
        queue <node*> q;
        bool leaf = false;
        node* l = NULL;
        node* r = NULL;
        q.push(head);
        while (!q.empty()){
            head = q.front();
            l = head->left;
            r = head->right;
            if ((leaf && (l != NULL || r != NULL))
                ||
                (l == NULL && r != NULL)){
                return false;
                }
            if (l != NULL){
                q.push(l);
            }
            if (r != NULL){
                q.push(r);
            }
            else{
                leaf = true;
            }
            q.pop();
        }
    
        return true;
    }
    
    int main(){
        node* head = new node(1);
        head->left = new node(2);
        head->right = new node(3);
        head->left->left = new node(4);
        head->left->right = new node(5);
        head->right->left = new node(6);
        cout << isCST(head) << endl;
    }
    
    
    
    展开全文
  • 判断搜索二叉树和完全二叉树 题目描述 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 回顾: 搜索二叉树 二叉查找树(Binary ...

    判断搜索二叉树和完全二叉树

    题目描述

    给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。

    示例1
    输入    {2,1,3}
    返回值  [true,true]
    

    回顾:

    1. 搜索二叉树
      二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
    2. 完全二叉树
      一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
    package 牛客.;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /*
     * @Author   helen
     * @Date     2021/4/15 15:01
     * @Descriptions
     * 题目描述
        给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。
        示例1
        输入    {2,1,3}
        返回值  [true,true]
     */
    public class 判断搜索二叉树和完全二叉树 {
        public boolean[] judgeIt (BTreeNode<Integer> root) {
            // write code here
            boolean[] result = {true,true};
            if(root == null)
                return result;
    
            //判断搜索二叉树  使用中序遍历搜索判断
            Stack<BTreeNode<Integer>> stack = new Stack<>();
            ArrayList<Integer> list = new ArrayList<>();
            BTreeNode<Integer> cur = root;
            while(!stack.isEmpty()){
                if(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }else {
                    cur = stack.pop();
                    list.add(cur.data);
                    cur = cur.right;
                }
            }
            //判断遍历时是否是从小到大排序
            for (int i = 1; i < list.size(); i++) {
                if(list.get(i) < list.get(i - 1)){
                    result[0] = false;
                    break;
                }
            }
    
            //判断完全二叉树
            Queue<BTreeNode<Integer>> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                BTreeNode<Integer> node = queue.peek();
                //2.1如果该节点两个孩子都有,则直接poll,然后把左右结点入队
                if(node.left != null && node.right != null){
                    queue.poll();
                    queue.add(node.left);
                    queue.add((node.right));
                }
                //2.2如果该节点左孩子为空,右孩子不为空,则一定不是完全二叉树
                if(node.left == null && node.right != null) {
                    result[1] = false;
                    break;
                }
                //2.3如果该节点左孩子不为空,右孩子为空 或者 左右孩子均为空,
                // 则该节点之后的所有结点均为叶子结点,把叶子结点直接poll出来
                if((node.left != null && node.right == null) 
                    || (node.left == null && node.right == null)){
                    if(node.left != null && node.right == null)
                        queue.add(node.left);
                    queue.poll();
                    while (!queue.isEmpty()){
                        node = queue.peek();
                        //到此,如果还存在不是叶子结点的结点的话,则不是完全二叉树
                        if(node.left == null && node.right == null)
                            queue.poll();
                        else {
                            result[1] = false;
                            break;
                        }
                    }
                }
            }
            return result;
    
        }
        public static void main(String[] args) {
            判断搜索二叉树和完全二叉树 obj = new 判断搜索二叉树和完全二叉树();
            BTree<Integer> tree =  new BTree<>();
            for (int i = 0; i < 10; i++) {
                tree.RandomCreatTree(tree.root, i);
            }
            final boolean[] booleans = obj.judgeIt(tree.root);
            System.out.println(booleans[0] + " " + booleans[1]);
        }
    
    }
    
    
    展开全文
  • 牛客链接 1. 题目考点 搜索二叉树定义 搜素二叉树的判定(性质) 二叉树的中序遍历 完全二叉树定义 完全二叉树的判定(性质) ...搜索二叉树的判定:中序遍历搜索二叉树是一个升序序列 public boolean inOrder(TreeNo

    牛客链接

    1. 题目考点

    1. 搜索二叉树定义
    2. 搜素二叉树的判定(性质)
    3. 二叉树的中序遍历
    4. 完全二叉树定义
    5. 完全二叉树的判定(性质)
    6. 二叉树的层次遍历

    2. 考点解析

    1. 搜索二叉树(又叫二叉排序树、二叉查找树、二叉搜索树)的定义:
      1. 空树是搜索二叉树
      2. 若左子树不为空,左子树的根节点关键字 < 根节点关键字
      3. 若右子树不为空,右子树的根节点关键字 > 根节点关键字
      4. 左右子树是搜索二叉树
    2. 搜索二叉树的判定:中序遍历搜索二叉树是一个升序序列
    // 中序遍历当时卡克了,中序遍历是访问节点的操作在第二次经过该节点时发生
    public boolean inOrder(TreeNode root) {
       	ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur); // 第一次经过节点
                cur = cur.left;
            } else {
                cur = stack.pop(); // 第二次经过节点
                list.add(cur.val); // 访问操作在第二次经过节点时发生
                cur = cur.right;
            }
        }
        // 判断是否是一个升序序列
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) >= list.get(i + 1)) return false;
        }
        return true;
    }
    
    1. 完全二叉树的定义:略
    2. 完全二叉树的性质:叶子节点只能在最后一层或者倒数第二层,最后一层叶子节点靠近最左边
    3. 完全二叉树的判定:
      1. 第一种方法:入队时判断节点左右孩子情况,分 4 种情况分类讨论
      2. 第二种方法:入队时不考虑左右孩子,遇到空节点之后剩余的应当全是空节点
      3. 第二种方法比第一种简单,但是时间复杂度比第一种高
    // 第一种方法
    public boolean bfs(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 1. 若左右孩子不为空,则入队
            if (node.left != null && node.right != null) {
                queue.offer(node.left);
                queue.offer(node.right);
              // 2. 若左孩子为空且右孩子不为空,不符合完全二叉树性质,退出
            } else if (node.left == null && node.right != null) {
                return false;
              // 3. 若左孩子不空且右孩子为空,则结束循环,检查队列中剩余元素是否都是叶子节点
            } else if (node.left != null && node.right == null) {
                queue.offer(node.left);
                break;
              // 4. 若左右孩子都为空,同样结束循环,检查队列中剩余元素是否都是叶子节点
            } else break;
        }
        // 此时队列为空,满足完全二叉树性质
        if (queue.isEmpty()) return true;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) ; 
            else return false;
        }
        return true;
    }
    
    // 第二种方法:不考虑节点孩子情况,当第一次遇到空节点时,判断队列中剩余元素是否全是空节点
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (queue.peek() != null) {
            TreeNode node = queue.poll();
            // 不管节点左右孩子是否为空,统统入队,直到对头节点为空
            queue.offer(node.left);
            queue.offer(node.right);
        }
     	// 判断队列剩余节点是否全为空
        while (!queue.isEmpty() && queue.peek() == null) {
            queue.poll();
        }
        return queue.isEmpty();
    }
    
    展开全文
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] import java.util.*; /* * public class TreeNode { * int val = ...

    题目描述

    给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。

    示例1

    输入

    {2,1,3}

    返回值

    [true,true]
    
    
    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布尔型一维数组
         */
        /**
         * 假设一个二叉搜索树具有如下特征:
         *
         * 节点的左子树只包含小于当前节点的数。
         * 节点的右子树只包含大于当前节点的数。
         * 所有左子树和右子树自身必须也是二叉搜索树。
         *       2
         *.   1.    3
         * 是二叉搜索树
         *       1
         *    2     3
         * 非二叉搜索树
         *
         *思路:中序遍历的结果是从小到大排列,故采用中序遍历,对节点值进行比较,如果出现当前节点值小于前一个节点值则不是二叉搜索树。
         */
        //是否是二叉搜索树
        boolean isBstTreeFlg = true;
        //上一个节点值
        int preNodeVal = Integer.MIN_VALUE;
        
        public boolean[] judgeIt (TreeNode root) {
            
            boolean[] result = new boolean[2];
            
            if(root == null){
                result[0] = true;
                result[1] = true;
                return result;
            }
            
            isBstTree(root);
            
            result[0] = isBstTreeFlg;
                   
            result[1] = isCompleteTree(root);
    
            return result;
        }
        
        //中序遍历
        public void isBstTree(TreeNode root){
            
            if(root == null || !isBstTreeFlg){
                return;
            }
            
            isBstTree(root.left);
            
            if(root.val > preNodeVal){
                preNodeVal = root.val;
            }else{
                //中序遍历 如:2 1 3 2节点 < 1节点 说明不是二叉搜索树 所以直接结束
                isBstTreeFlg = false;
                return;
            }
            
            isBstTree(root.right);
        }
        
        public boolean isCompleteTree(TreeNode root){
            
            if(root == null){
                return false;
            }
            
            // 1. 先对树进行层序遍历
            // 如果这个标记为 false, 说明还是处在第一阶段
            // 如果这个标记为 true , 接下来的节点就不能有子树
            // 也就是第二阶段开始了
            int flg = 1;//第一阶段:1 第二阶段:2
            
            LinkedList<TreeNode> queue = new LinkedList();
            
            queue.add(root);
            
            while(!queue.isEmpty()){
                TreeNode temp = queue.poll();
                
                if(flg == 1){
                    
                    // 合格的状态, 继续往下遍历.
                    // 就把左右子树加入队列就行了
                    if(temp.left != null && temp.right != null){
                        queue.offer(temp.left);
                        queue.offer(temp.right);
                    }else if(temp.left == null && temp.right != null){
                        // 这种情况铁定不是完全二叉树
                        return false;
                    }else if(temp.left != null && temp.right == null){
                        // 这是临界状态, 开启第二阶段
                        queue.offer(temp.left);
                        //开启第二阶段
                        flg = 2;
                    }else{
                        // 左右子树都为空, 开启第二阶段
                        flg = 2;
                    }
                }else{
                    //开启第二阶段
                    // 第二阶段要求节点必须没有子树. 只要子树存在, 就不是完全二叉树
                    if(temp.left != null || temp.right != null){
                        return false;
                    }
                }
            }
            
            return true;
        }
    }

     

    展开全文
  • 题目 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 ...
  • 1、搜索二叉树的定义: 它是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,...如何判断一棵二叉树是否是搜索二叉树? 答:只需要判断该二叉树的中序遍历是否从小到大有序,即升序。 2、完全二叉树: ...
  • 搜索二叉树:它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树...
  • 搜索二叉树为中序遍历升序判断 通过改变非递归版本的打印行为部分即可 import sys class Node(object): def __init__(self,val=None): self.val = val self.left = None self.right = None #非递归版本 #...
  • 举例: size balance tree简称sb数 平衡性很重要,是用来解决...较中序遍历时相邻两个结点的大小,只要有一个结点的值小于其后继结点的那就不是搜索二叉树搜索二叉树不出现重复节点。 初级5 时间: 02.19.19 ...
  • 判断一个二叉树是否为搜索二叉树

    千次阅读 2018-05-27 19:28:18
    判断搜索二叉树 由上图可知,如果搜索二叉树按照中序遍历的方式遍历所有的点,那么这些点肯定是递增的,我们只要在中序遍历输出编号时加一个判断条件(当前输出的编号和前一个输出的编号的大小关系)就可以做到判断...
  • 其中,判断搜索二叉树,只需要中序遍历一次,取出值,看是否是递增即可。 判断是否是完全二叉树,只需要按层遍历一次,找到第一个null的节点即可。创建一个队列,进行存储,存储每一个节点,然后按顺序拿出来,找到...
  • /* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * * @param root TreeNode类 * @return bool布尔型 */ function findleft(root) ... .
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 备注: n≤500000n \leq 500000n≤500000 假设一个二叉搜索树具有...
  • 判断搜索二叉树:递归。递归函数返回是否是搜索二叉树;递归函数内部需要完成左子树、根、右子树的大小对比。 判断完全二叉树:算法摘自百度百科。 代码: import java.util.*; /* * public class TreeNode { * ...
  • 判断搜索二叉树看我之前的文章LeetCode系列98—验证二叉搜索树 完全二叉树可以这样来判断: 层次遍历直至遇到第一个空节点 完全二叉树在遇到空节点之后剩余的应当全是空节点 public boolean isCompleteTree...
  • **搜索二叉树(BST):**所谓搜索...思想:怎么判断是否是一棵搜索二叉树呢,我们可以通过中序遍历这棵二叉树的方法,如果这个序列是单调递增的那么这棵树一定是搜索二叉树。使用中序遍历的非递归方法可以很简单的就...
  • 判断一棵树是否是二叉搜索树:中序遍历树,如果序列是升序序列则是二叉搜索树,否则不是二叉搜索树。 判断一棵树是否是完全二叉树:采用层次遍历的方式 如果一个节点左右孩子均存在,那么就poll,并把其左右孩子加入...
  • 搜索二叉树判断

    2019-01-11 15:55:41
    文章目录搜索二叉树的判断搜索二叉树思路1思路2关于作者 搜索二叉树的判断 比较常见的面试题。 搜索二叉树 概念不说了,相信各位同学都是知道的,不知道的Google一下。 思路1 起初看到这个题,本来想着直接找递归...
  • 许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。 二叉树(BinaryTree)是n(n≥0)个结点的有限集,它...
  • 1.二叉搜索树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上...# 中序遍历情况下,值递增则为二叉树 def isBSTree(head): minimum = -100000 # 设定一个最小值 ...
  • 判断一棵二叉树是否为二叉搜索

    千次阅读 2019-05-09 22:12:15
    判断一棵二叉树是否为二叉搜索树 二叉搜索树定义 二叉搜索树(Binary Search Tree)(又:二叉查找树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均...
  • 搜索二叉树:中序遍历为递增序列,如果不是,返回false 完全二叉树:层次遍历中,不... //判断是否为搜索二叉树 中序遍历即可,若非递增那么不是 bool BSTJudge(TreeNode* root) { stack<TreeNode*> ...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 备注: n \leq 500000n≤500000 Python代码: # class ...
  • 判断搜索二叉树 : 创建一个全局变量保存当前结点的前一个结点,中序遍历二叉树判断当前结点的数值是否比前一个结点大。 也可以中序遍历数将遍历到的结点保存在一个集合中,检查是否递增。 判断完全二叉: 横向遍历...
  • # coding=utf-8 """ question: ...搜索二叉树的父节点值大于其左子树的所有值,小于其右子树的所有值 """ def judge(nums): if not nums: return False elif len(nums) == 1: # 递归出口 ...
  • 判断一棵二叉树是否为搜索二叉树和完全二叉树(C++牛客网)
  • 有一个整数型列表,判断该列表是否为对应二叉搜索树的后序遍历结果 ''' 二叉搜索树 二叉排序树 二叉查找树 前序遍历 中序遍历 后序遍历 根节点 算法: 1. 找到根节点 2. 遍历序列,找到第一个大于根节点的元素i,则i...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,259
精华内容 20,103
关键字:

判断搜索二叉树