精华内容
下载资源
问答
  • 判断搜索二叉树 搜索二叉树:对每一个节点来说,左边的小于它,右边的大于它。 中序遍历(左中右)的结果在递增,就是搜索二叉树。 判断以x为头的子树是不是二叉搜索树 需要向左树要:左树是不是搜索二叉树,和max...

    在这里插入图片描述

    判断搜索二叉树

    搜索二叉树:对每一个节点来说,左边的小于它,右边的大于它。
    在这里插入图片描述
    中序遍历(左中右)的结果在递增,就是搜索二叉树。

    判断以x为头的子树是不是二叉搜索树
    在这里插入图片描述
    需要向左树要:左树是不是搜索二叉树,和max
    需要向右树要:右树是不是搜索二叉树,和min

    递归需要返回的信息:整棵树是不是搜索树,整棵树的max,整棵树的min
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述在这里插入图片描述二叉树的递归套路:利用可以向左右子树要信息的情况下,我整理出我可能性需要的信息,然后把信息的返回值在左树和右树上求并集。

    代码:

     //判断是不是二叉搜索树
        private static boolean BSTprocess(TreeNode node,int min,int max) {
            if(node==null) return true;
            if(node.val<min || node.val>max){
                return false;
            }
            return BSTprocess(node.left,min,node.val) &&BSTprocess(node.right,node.val,max);
        }
    

    判断满二叉树

    二叉树的最大高度为h,节点数为N,要满足N=2^h -1
    当不用二叉树的递归套路去做:求最大高度,求节点数,看满不满足关系
    用二叉树的递归套路去做:信息体包括以该节点为头的二叉树的最大高度和节点数
    在这里插入图片描述

    代码:

     //判断是不是满二叉树
        private static boolean isFull(TreeNode node) {
            Info info=Fullprocess(node);//算该节点的子树的高度和节点数
            //高度和节点数是否满足公式
            int nodes = info.nodes;
            int height = info.height;
            if(nodes==Math.pow(2,height)-1){
                return true;
            }
            return false;
        }
    
        private static Info Fullprocess(TreeNode node) {
            if(node==null) return new Info(0,0);
    
            Info leftInfo = Fullprocess(node.left);
            Info rigtInfo = Fullprocess(node.right);
    
            int height=Math.max(leftInfo.height,rigtInfo.height)+1;
            int nodes=leftInfo.nodes+rigtInfo.nodes+1;//算上父节点
    
            return new Info(nodes,height);
        }
    

    整体代码:

    package Tree;
    
    
    
    public class IsBSTAndFull {
        public static class TreeNode{
            int val = 0;
            TreeNode left = null;
            TreeNode right = null;
    
            public TreeNode(int val) {
                this.val = val;
            }
        }
        //判断满二叉树结构
        public static class Info{
            public int nodes;
            public int height;
    
            public Info(int nodes, int height) {
                this.nodes = nodes;
                this.height = height;
            }
        }
    
        //判断是不是二叉搜索树
        private static boolean BSTprocess(TreeNode node,int min,int max) {
            if(node==null) return true;
            if(node.val<min || node.val>max){
                return false;
            }
            return BSTprocess(node.left,min,node.val) &&BSTprocess(node.right,node.val,max);
        }
    
        //判断是不是满二叉树
        private static boolean isFull(TreeNode node) {
            Info info=Fullprocess(node);//算该节点的子树的高度和节点数
            //高度和节点数是否满足公式
            int nodes = info.nodes;
            int height = info.height;
            if(nodes==Math.pow(2,height)-1){
                return true;
            }
            return false;
        }
    
        private static Info Fullprocess(TreeNode node) {
            if(node==null) return new Info(0,0);
    
            Info leftInfo = Fullprocess(node.left);
            Info rigtInfo = Fullprocess(node.right);
    
            int height=Math.max(leftInfo.height,rigtInfo.height)+1;
            int nodes=leftInfo.nodes+rigtInfo.nodes+1;//算上父节点
    
            return new Info(nodes,height);
        }
    
    
        public static void main(String[] args) {
            TreeNode node=new TreeNode(3);
            node.left=new TreeNode(1);
            node.right=new TreeNode(20);
            //node.right.left=new TreeNode(15);
           // node.right.right=new TreeNode(27);
            boolean b=BSTprocess(node,Integer.MIN_VALUE,Integer.MAX_VALUE);
            System.out.println(b);
    
            //判断满二叉树
            boolean bb= isFull(node);
            System.out.println(bb);
    
        }
    
    
    
    
    }
    

    判断一个树是不是平衡二叉树

    平衡二叉树:每一棵子树,左树和右树的高度差不超过1(<=)
    需要三个信息:左树是不是平衡树,右树是不是平衡树,左右树的高度差是不是不超过1

    代码:

    package Tree;
    
    public class BalanceTree {
        
        public static class TreeNode{
            int val;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(int val) {
                this.val = val;
            }
        }
    
        public static class Info{
            boolean Balance;
            int height;
    
            public Info(boolean balance, int height) {
                Balance = balance;
                this.height = height;
            }
        }
    
        //判断是不是平衡树
        private static boolean isBalance(TreeNode node) {
            Info info=BalanceProcess(node);
            return info.Balance;
        }
    
        private static Info BalanceProcess(TreeNode node) {
            if(node==null) return new Info(true,0);
            //判断左右子树是不是平衡树
            Info leftInfo = BalanceProcess(node.left);
            Info rightInfo = BalanceProcess(node.right);
            int height=Math.max(leftInfo.height,rightInfo.height)+1;//加上根节点的层书
            //再判断左右子树的高度差是否不超过1
            if(Math.abs(leftInfo.height-rightInfo.height)<2){
                if(leftInfo.Balance && rightInfo.Balance){
                    return new Info(true,height);
                }
            }
    
            return new Info(false,height);
        }
    
    
        public static void main(String[] args) {
            TreeNode node=new TreeNode(3);
            //node.left=new TreeNode(1);
            node.right=new TreeNode(20);
            //node.right.left=new TreeNode(15);
            //node.right.right=new TreeNode(27);
            //node.right.right.left=new TreeNode(30);
            //node.right.right.right=new TreeNode(31);
            boolean b=isBalance(node);
            System.out.println(b);
        }
    
    
    }
    

    找最近的公共祖先节点

    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    如果左树上有一个,右树上有一个,那么根节点就是最近的公共祖先。
    如果两个结点全在左树上或者全在右树上。
    三个信息:最近的公共祖先是否为空(找没有找到),整棵树上是否发现了o1,整棵树上是否发现了o2
    在这里插入图片描述在这里插入图片描述当是在两侧分别发现的两个结点,那么根节点就是最近的公共祖先
    在这里插入图片描述还要考虑根节点是不是两个节点中的一个。
    如果x等于o1(o1),那说明在整棵树上发现了o1(o2)。
    在左右子树上只发现了o1,但是在根节点发现了o2,那么公共祖先就是根节点

    在这里插入图片描述
    在这里插入图片描述

    判断一个数是否为完全二叉树?

    在这里插入图片描述
    判断条件:宽度优先遍历,满足两个条件
    1、遍历的任何结点不可能有右孩子没有左孩子
    2、如果遇到了孩子不全的结点,那么后面的结点必为叶子节点(左右孩子为空)
    在这里插入图片描述5是一个转折
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述如果你之前遇到过不双全的结点,但此时的结点左右孩子不为空(不是叶子节点)。说明该树不是完全二叉树

    在这里插入图片描述isMeet一旦改为true,后面的节点一定要是叶子节点

    展开全文
  • 单纯的搜索二叉树并不能保证平衡,它的平衡性受制于输入数据,输入的顺序不好(1 2 3 4 5)会导致搜索二叉树变成一条线,这样的时间复杂度是O(n) 下面是不同的平衡搜索二叉树 AVL树 最严格的平衡性,任何一个节点左...

    单纯的搜索二叉树并不能保证平衡,它的平衡性受制于输入数据,输入的顺序不好(1 2 3 4 5)会导致搜索二叉树变成一条线,这样的时间复杂度是O(n)

    下面是不同的平衡搜索二叉树

    • AVL树:有最严格的平衡性,任何一个节点左子树和右子树高度差不超过1,意味着每插入一个数可能都要调整。
      以下两种树平衡性没有AVL树那么严格,只是在调整的时候策略不同。都能做到增删改查时间复杂度O(logn),差的只是常数项操作的数量。
    • 红黑树:
    • SB树:

    练习题1 大楼轮廓

    在这里插入图片描述

    给你一组数:(1,6,4) (2,4,3) (5,8,5) (7,10,2),代表大楼的起始位置、终止位置和高度,例如(1,6,4)代表大楼起始位置1,终止位置6,高度是4。让你求这些大楼的轮廓,如上图红色所示。

    我们注意到,大楼的轮廓只有在高度发生变化时才会改变,将他给的数据弄成这种形式,以(1,6,4)为例:

    • (1,4,up) 代表1位置有个高度4上去了
    • (6,4,down) 代表6位置有个高度4下来了

    将给出的所有数据都处理成这种形式,然后按照位置从小到大排序,结果如下:

    • (1,4,up) (2,3,up) (4,3,down) (5,5,up) (6,4.down) (7,2,up) (8,5,down) (10, 2,down)

    开始时高度为0,遍历上述结果,到第一个位置,将(4,1)加到treeMap中,代表目前为止4出现了一次;到2位置,将(3,1)加到teeMap中,由于此时(4,1)还在,因此2位置的最大高度仍然是4;到4位置,由于是down,所以将(3,1)的次数减1,此时为0,即treeMap中没有(3,1)了。5位置,在treeMap中插入(5,1),此时treeMap中最大的是(5,1)表示到5位置时最大高度变了(由4变为5);6位置把treeMap中的(4,1)减1,此时treeMap中最大的仍然是(5,1);7位置在treeMap中添加了(2,1),但此时最大的仍然是(5,1);8位置将treeMap中的(5,1)减1,此时treeMap中最大的是(2,1),代表8位置的最大高度发生了变化(由5变为2);10位置将treeMap中的(2,1)减1,此时treeMap中无元素,最大值记为0,代表10位置的最大高度发生变化(由2变为0),至此便利结束后。

    回看上述过程,其实就是先他给的数据重新处理,根据位置从小到大排序,然将每个位置的最高高度记录下来。代码如下:

    这是将给出的数据转换后的结构:

    class Node {
        boolean isUp;
        int pos;
        int height;
    
        public Node(boolean isUp, int pos, int height) {
            this.isUp = isUp;
            this.pos = pos;
            this.height = height;
        }
    }
    

    正式开始:

    public class Building {
        public List<List<Integer>> solution(int[][] buildings) {
            if (buildings == null || buildings.length == 0) {
                return null;
            }
    
            Node[] nodes = new Node[buildings.length * 2];
            for (int i = 0; i < buildings.length; i++) {
                nodes[2*i] = new Node(true, buildings[i][0], buildings[i][2]);
                nodes[2*i+1] = new Node(false, buildings[i][1], buildings[i][2]);
            }
    
            Arrays.sort(nodes, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    return o1.pos - o2.pos;
                }
            });
    
            TreeMap<Integer, Integer> htMap = new TreeMap<>();
            TreeMap<Integer, Integer> pmMap = new TreeMap<>();
    
            for (int i = 0; i < nodes.length; i++) {
                if (nodes[i].isUp) {
                    if (!htMap.containsKey(nodes[i].height)) {
                        htMap.put(nodes[i].height, 1);
                    }else {
                        htMap.put(nodes[i].height, htMap.get(nodes[i].height)+1);
                    }
                }else {
                    if (htMap.get(nodes[i].height) == 1) {
                        htMap.remove(nodes[i].height);
                    }else {
                        htMap.put(nodes[i].height, htMap.get(nodes[i].height)-1);
                    }
                }
                if (htMap.isEmpty()) {
                    pmMap.put(nodes[i].pos, 0);
                }else {
                    pmMap.put(nodes[i].pos, htMap.lastKey());
                }
            }
    
            int height = 0;
            int start = 0;
            List<List<Integer>> res = new ArrayList<>();
            // 这里的代码是leetcode版本的,下面注释部分是左神的版本,功能差不多,只是输出格式不同
            for (Map.Entry<Integer, Integer> entry: pmMap.entrySet()){
                int curPos = entry.getKey();
                int curHei = entry.getValue();
                if (height != curHei) {
                    List<Integer> record = new ArrayList<>();
                    record.add(curPos);
                    record.add(curHei);
                    res.add(record);
                    height = curHei;
                }
    
    //			  注释部分是左神的代码
    //            if (height != curHei) {
    //                if (height != 0) {
    //                    List<Integer> record = new ArrayList<>();
    //                    record.add(start);
    //                    record.add(curPos);
    //                    record.add(height);
    //                    res.add(record);
    //                }
    //                start = curPos;
    //                height = curHei;
    //            }
            }
        return res;
    
        }
    
        public static void main(String[] args) {
            int[][] buildings = new int[][]{{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
    
            List<List<Integer>> res = new Building().solution(buildings);
            System.out.println(res.toString());
        }
    }
    
    结果:
    [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
    

    练习题2 累加和的最长子数组

    题目:给你一个数组,里面可能有正数、负数和0,有一个目标值target,让你找出相加等于target的最长子数组是啥。

    例子:[7 3 2 1 1 7 -6 -1 7],target=7,那么最长子数组应该是:[3 2 1 1 7 -6 -1]

    分析:
    对于数组中的每一个位置,都求一下以它结尾且子数组之和等于target的最长子数组,当所有的位置都求完之后结果也就出来了。

    如何求某个位置的最长子数组(之和等于target)呢?我们定义一个变量sum,让他从0位置就开始累加,假设要求i位置的最长子数组,那么sum就表示从0位置加到i位置的所有数的和,那么sum-target=remain,表示只要找到了remain,i位置就必然存在这么一个子数组(但是不是最长的还不知道,要遍历所有位置之后才知道),注意,这个remain我们记录它第一次出现的位置,具体见如下详细说明:

    • 设target=7,开始sum=0,维持一个hashMap,由于不遍历任何元素也能得到0,所以0的位置设为-1,那么hashMap = {0:-1}
    • 然后i=0,sum=sum+7=7,再用7-target=0,也就是说只要0位置之前出现了0,那对于0位置来说就肯定能找到一个字数组使其相加等于target(7),由hashMap可知,0位置最早出现在-1位置,因此-1的下一个位置(0)和i(0)就构成了一个和为7的子数组[7]。之后在hashMap中添加一条 {7:0},表示7最早在0位置出现;
    • i=1,sum=sum+3=10,而10-7=3,但hashMap中没有出现过3,所以以1位置结尾不可能出现和为7的子数组。但要将 {10:1} 添加进hashMap,表示10最早出现在1位置;
    • i=2,sum=sum+2=12,而12-7=5,但hashMap中没有5,即不会有以2位置尾的子数组之和为7。将 {12:2} 加到hashMap中,表示12最早出现在2位置;
    • i=3,sum=sum+1=13,而13-7=6,但hashMap中没有6,即不会有以3位置结尾的子数组之和为7。将 {13:3} 加到hashMap中,表示13最早出现在3位置;
    • i=4,sum=sum+1=14,而14-7=7,hashMap中有7,其最早出现的位置是0,因此子数组[1:4]之和为7,但不能确定是否为最长的,因此先用一个变量记录下来;将 {14:4} 加到hashMap中;
    • i=5,sum=sum+7=21,21-7=14,hashMap有14,他最早出现的位置是4,因此子数组[4:5]之和为7,但其长度小于子数组[1:4]。将 {21:5} 加到hashMap中;
    • i=6,sum=sum+(-6)=15,15-7=8,hashMap没有8,将 {15: 6} 添加到hashMap中;
    • i=7,sum=sum+(-1)=14,14-7=7,hashMap中有7,其最早出现的位置是0,因此子数组[1:7]之和为7,且长度比子数组[1:4]更长,但这时 不将 {7:7} 添加进hashMap中,因为我们要保存最早出现的;
    • i=8,sum=sum+(7)=21,21-7=14,hashMap中有14,其最早出现的位置是4,因此子数组[4:8]之和为7,但没有子数组[1:7]长,不将 {21:8} 加到hashMap中;
    • 整个过程结束
    public class SubArrSum {
        public void solution(int[] arr, int target) {
    
            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);
            int sum = 0;
            int len = 0;
            for (int i = 0; i < arr.length; i++) {
                sum += arr[i];
                if (map.containsKey(sum-target)) {
                    len = Math.max(len, i - map.get(sum-target));
                }
                if (!map.containsKey(sum)) {
                    map.put(sum, i);
                }
            }
            System.out.println(len);
        }
    
        public static void main(String[] args) {
            int[] arr = new int[]{7, 3, 2, 1, 1, 7, -6, -1, 7};
            new SubArrSum().solution(arr, 7);
        }
    }
    
    结果:
    7
    

    上题的变形 1

    给你一个数组,有奇数有偶数,让你找技术和偶数个数相同的最长子数组。

    把技术变成-1,偶数变成1,求和等于0的最长子数组即可。

    上题的变形 2

    一个数组有0 1 2三种值若干,让你求1和2数量相同的最长子数组是多少。

    把2变成-1,找和为0的最长子数组即可。

    练习题3 (使用到了累加和的最长子数组思想)

    在这里插入图片描述

    给你一个数组,可以随意进行划分,每个划分后的组元素 异或 可能为0,也可能不为0,让你返回使子数组异或为0数量最多的子数组个数。

    对于[0,i]的划分,假设存在这么一种最优划分,将[0,i]分为若干个组,那么i作为最后一组的最后一个元素,最后一组只可能有两种可能:

    • 最后一组所有元素异或为0
    • 最后一组中所有元素异或不为0

    对于第一种情况,

    练习题4 求一棵二叉树的最大搜索二叉子树

    搜索二叉树是指对于二叉树上的任意一个节点,它的左孩子一定小于自己,右孩子一定大于自己。而子树是指一个节点及它的左右子树,不能只要其左子树或右子树,那样不叫子树。

    如下图所示,红色区域就是整个二叉树的最大搜索二叉子树:
    在这里插入图片描述
    而下图红色区域不是最大搜索二叉树,因为6的右子树4没有被包含进去:
    在这里插入图片描述
    分析:
    对于一棵二叉树,它的最大搜索二叉子树只会有三种情况:

    • 从根节点的左子树中产生,但不一定是根节点的直接左节点,如上面第一张图所示;
    • 从根节点的右子树中产生,但不一定是根节点的直接右节点;
    • 整棵树都是搜索二叉树,这意味着根节点的左子树和右子树全是搜索二叉树,而根节点的值也恰好合适,如下图所示:
      在这里插入图片描述
      解这道题的时候,可以先假设对于二叉树上当前的某个节点i,通过某个 黑盒 得到了其左子树的信息和右子树的信息。那么这个信息都应该包含什么内容呢?首先其左子树的最大搜索二叉树的头节点其右子树的最大搜索二叉树的头节点是肯定要得到的;最大搜索二叉树的大小也需要得到;最大搜索二叉树的最大值和最小值也应该知道,因为节点i要通过这个信息判断自己能不能和左右子树拼成一个大的所有二叉树。

    如上图所示,假设8就是节点i,得到了左子树的信息,大小是3,头节点是6,最大值是7,最小值是5;得到了右子树的信息,大小是3,头节点是10,最大值是13,最小值是9,而8大于7,8小于9,因此8可以和左右子树拼成一个大的搜索二叉树。

    因此我们需要将子树返回的信息用一个结构保存起来:

    class Data{
        int size;  // 最大搜索二叉子树的大小
        TreeNode root;  // 最大搜索二叉子树的根
        int max;  // 最大搜索二叉子树的最大值
        int min;  // 最大搜索二叉子树的最小值
    
        public Data(int size, TreeNode root, int max, int min) {
            this.size = size;
            this.root = root;
            this.max = max;
            this.min = min;
        }
    }
    

    代码:

    class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
    
        public TreeNode(int value) {
            this.value = value;
        }
    }
    
    public class MaxSearchTree {
        public Data solution(TreeNode root) {
            if (root == null) {
                return new Data(0, null, Integer.MIN_VALUE, Integer.MAX_VALUE);
            }
            TreeNode leftNode = root.left;
            Data leftData = solution(leftNode);
    
            TreeNode rightNode = root.right;
            Data rightData = solution(rightNode);
    
            TreeNode curHead = leftData.size > rightData.size? leftData.root: rightData.root;
            int curSize = Math.max(leftData.size, rightData.size);
            if (leftData.root == leftNode && rightData.root == rightNode && root.value > leftData.max && root.value < rightData.min) {
                curHead = root;
                curSize = leftData.size + rightData.size + 1;
            }
    
            return new Data(curSize, curHead, Math.max(root.value, Math.max(leftData.max, rightData.max)), Math.min(root.value, Math.min(leftData.min, rightData.min)));
        }
    
        public static void main(String[] args) {
            TreeNode n13 = new TreeNode(13);
            TreeNode n9 = new TreeNode(9);
            TreeNode n10 = new TreeNode(10);
            TreeNode n5 = new TreeNode(5);
            TreeNode n6 = new TreeNode(6);
            TreeNode n7 = new TreeNode(7);
            TreeNode n8 = new TreeNode(8);
    
            n8.left = n6;
            n8.right = n10;
            n6.left = n5;
            n6.right = n7;
            n10.left = n9;
            n10.right = n13;
    
            Data res = new MaxSearchTree().solution(n8);
            System.out.println(res.size);
        }
    }
    
    结果:
    7
    

    练习题 5

    在这里插入图片描述
    最远距离可能有三种情况:

    • 在根节点的左子树:
      在这里插入图片描述

    • 在根节点的右子树:同上

    • 通过根节点,此时最远距离即为左边的深度+1+右边的深度
      在这里插入图片描述

    代码:

    class returnType{
        int height;
        int maxDis;
    
        public returnType(int height, int maxDis) {
            this.height = height;
            this.maxDis = maxDis;
        }
    }
    
    public class MaxDis {
        public returnType solution(TreeNode root) {
            if (root == null) {
                return new returnType(0,0);
            }
            returnType leftRes = solution(root.left);
            returnType rightRes = solution(root.right);
    
            int includeCur = leftRes.height + 1 + rightRes.height;
            int p1 = leftRes.maxDis;
            int p2 = rightRes.maxDis;
            includeCur = Math.max(includeCur, Math.max(p1, p2));
            int curHeight = Math.max(leftRes.height, rightRes.height) + 1;
    
            return new returnType(curHeight, includeCur);
        }
    
        public static void main(String[] args) {
            TreeNode n13 = new TreeNode(13);
            TreeNode n9 = new TreeNode(9);
            TreeNode n10 = new TreeNode(10);
            TreeNode n5 = new TreeNode(5);
            TreeNode n6 = new TreeNode(6);
            TreeNode n7 = new TreeNode(7);
            TreeNode n8 = new TreeNode(8);
    
            n8.left = n6;
            n8.right = n10;
            n6.left = n5;
            n6.right = n7;
            n10.left = n9;
            n10.right = n13;
    
            System.out.println(new MaxDis().solution(n8).maxDis);
        }
    }
    
    结果:
    5
    

    练习题 6

    在这里插入图片描述
    哎,偷个懒,代码先不写了,贴下链接:https://www.bilibili.com/video/BV1Uf4y1X7XC?p=45,大概90分钟左右。

    练习题 7 判断一颗树是否是平衡二叉树

    public class isBalance {
        public static class returnType{
            boolean isB;
            int h;
    
            public returnType(boolean isB, int h) {
                this.isB = isB;
                this.h = h;
            }
        }
    
        public static returnType solution(TreeNode root) {
            if (root == null) {
                return new returnType(true, 0);
            }
    
            returnType left = solution(root.left);
            if (!left.isB) {
                return new returnType(false, -1);
            }
            returnType right = solution(root.right);
            if (!right.isB) {
                return new returnType(false, -1);
            }
    
            if (Math.abs(left.h - right.h) > 1) {
                return new returnType(false, -1);
            }else {
                return new returnType(true, Math.max(left.h, right.h) + 1);
            }
        }
    }
    
    展开全文
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 备注: n≤500000n \leq 500000n≤500000 假设一个二叉搜索树具有...

    DESC:

    题目描述

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

    示例1

    输入

    {2,1,3}

    返回值

    [true,true]
    

    备注:

    n≤500000

    假设一个二叉搜索树具有如下特征:

        节点的左子树只包含小于当前节点的数。
        节点的右子树只包含大于当前节点的数。
        所有左子树和右子树自身必须也是二叉搜索树。

    百度百科中对完全二叉树的定义如下:

    若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

     

    CODE1:

    JAVA:

    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布尔型一维数组
         */
        public boolean[] judgeIt (TreeNode root) {
            // write code here
            //这个地方用的long型,是防止节点值正好是int型边界,leetcode int是不通过的,牛客可以
            boolean isSearchTree = checkSearchTree(root, Long.MIN_VALUE, Long.MAX_VALUE);
            boolean isWholeTree = checkWholeTree(root);
            return new boolean[]{isSearchTree, isWholeTree};
        }
        
        public boolean checkSearchTree(TreeNode node, long min, long max) {
                if (node == null) {
                    return true;
                }
    
                //注意这个地方,根据题意,相等为false,所以为>=和<=
                if (node.val <= min || node.val >= max) {
                    return false;
                }
    
                return checkSearchTree(node.left, min, node.val) && checkSearchTree(node.right, node.val, max);
            }
    
            public boolean checkWholeTree(TreeNode node) {
                LinkedList<TreeNode> nodeList = new LinkedList<>();
                if (node == null) {
                    return false;
                }
                nodeList.offer(node);
                while (true) {
                    TreeNode pop = nodeList.pop();
                    if (pop == null) {
                        break;
                    }
                    nodeList.offer(pop.left);
                    nodeList.offer(pop.right);
                }
    
                for (TreeNode nt : nodeList) {
                    if (nt != null) {
                        return false;
                    }
                }
                return true;
            }
    }

     

     

    NOTES1:

    1. 搜索树,通过限定左右子树的值域来判断
    2. 完全二叉树通过bfs进行判断,层序遍历后,当遇到null时,表明最后一个节点也遍历完了,如果是完全二叉树,那队列剩余的应该都是空节点,否则不是完全二叉树;

     

    CODE2:

    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布尔型一维数组
         */
        public boolean[] judgeIt (TreeNode root) {
            // write code here
            boolean isSearchTree = checkSearchTree(root, null, null);
            boolean isWholeTree = checkWholeTree(root);
            return new boolean[]{isSearchTree, isWholeTree};
        }
        
        public boolean checkSearchTree(TreeNode node, TreeNode minNode, TreeNode maxNode) {
                if (node == null) {
                    return true;
                }
    
                if ((minNode!= null && node.val <= minNode.val) || (maxNode!= null && node.val >= maxNode.val)) {
                    return false;
                }
    
                return checkSearchTree(node.left, minNode, node) && checkSearchTree(node.right, node, maxNode);
            }
    
            public boolean checkWholeTree(TreeNode node) {
                Queue<TreeNode> queue = new LinkedList<>();
                if (node == null) {
                    return false;
                }
                queue.offer(node);
                boolean flag = false;
                //这里循环条件不一样
                while (!queue.isEmpty()) {
                    TreeNode temp = queue.poll();
                    if (temp == null) {
                        flag = true;
                        continue;
                    }
                    if (flag) {
                        //按说已经到尾结点了,后面又有非空节点,说明非完全二叉树
                        return false;
                    }
                    queue.offer(temp.left);
                    queue.offer(temp.right);
                }
                return true;
            }
    }

     NOTES2:

    1. 相比code1, 搜索树值域直接传的是node,其值为区间值,递归中会自动封装应有的最大值和最小值;
    2. 完全二叉树,在bfs中一次判断,不在后续判断,其实和code1思路一样,只是合在了一起

     

    展开全文
  • 什么是搜索二叉树 用来搜索的二叉树就叫搜索二叉树,用来对数据进行二分查找,特点就是 1 所有左叶子节点的数都比当前节点小 2 所有右边节点的数都比当前节点大 思路:判断当前节点的左右子树是不是二叉树,...

    什么是搜索二叉树

            用来搜索的二叉树就叫搜索二叉树,用来对数据进行二分查找,特点就是

                    1 所有左叶子节点的数都比当前节点小

                    2 所有右边节点的数都比当前节点大

    思路:判断当前节点的左右子树是不是二叉树,如果是,说明当前节点有可能是,判断当前节点是不是二叉树

    可能情况:

            1 当前节点也是二叉查找树,条件就是左右子树是二叉查找树,并且当前节点的值大与左子树最大值,小于右子树最小值

            2 当前节点不是二叉查找树,条件  左右子树有一个不是二叉查找树树的当前节点就不是,并且当前节点的值大与左子树最大值,小于右子树最小值 这个条件不成立

    Node节点内容:

            1 当前节点之下是否是二叉查找树树 boolen

            2  当前节点下所有节点最大值

            3 当前节点下所有节点最小值

      代码

    package 算法.二叉树;
    
    import 算法.二叉树遍历;
    
    //判断二叉树是否是搜索二叉树
    public class test1 {
    
        /**
         * 树节点
         */
        public static class Node {
            //1 当前节点之下是否是二叉查找树树 boolen
           public boolean  flag;
            //2 当前节点下所有节点最大值
            public int max;
            //3 当前节点下所有节点最小值
            public int min;
    
    
            public int num;
            public Node left;
            public Node right;
    
            public Node(boolean flag, int max, int min) {
                this.flag = flag;
                this.max = max;
                this.min = min;
            }
        }
    
        public static Node process(Node node) {
            //当前节点为空返回
            if (node == null) {
                return  new Node(true,0,0);
            }
            Node l = process(node.left);
            Node r = process(node.right);
    
            //拿到左右节点之后 判断相应情况
    
            //1 如果满足二叉查找树 条件就是左右子树是二叉查找树,并且当前节点的值大与左子树最大值,小于右子树最小值
            node.flag = false;
            if (l.flag && r.flag && node.num > l.max&& node.num< r.min) {
                node.flag = true;
            } 
            // 2 更改max 和min的数据
            node.max = Math.max(l.max, r.max);
            node.min = Math.max(l.min, r.min);
            
            return node;
    
        }
    
    
        public static void main(String[] args) {
            process(null);
        }
    }
    

            

    展开全文
  • 牛客链接 1. 题目考点 搜索二叉树定义 搜素二叉树的判定(性质) 二叉树的中序遍历 完全二叉树定义 完全二叉树的判定(性质) ...搜索二叉树的判定:中序遍历搜索二叉树是一个升序序列 public boolean inOrder(TreeNo
  • 题目:判断二叉树是否为搜索二叉树和完全二叉树 思路: 判断搜索二叉树:递归。递归函数返回是否是搜索二叉树;递归函数内部需要完成左子树、根、右子树的大小对比。 判断完全二叉树:算法摘自百度百科。 代码: ...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 备注: n \leq 500000n≤500000 Python代码: # class ...
  • 判断一颗二叉树是否为搜索二叉树和完全二叉树 题目描述 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 思路 判断搜索二叉树 : 创建一个全局变量保存当前结点的前一个...
  • } //判断平衡二叉树(左孩子的值 父结点的值 右孩子的值) public boolean BSTprocess(TreeNode node,int min,int max){ if(node==null) return true; if(node.val|| node.val>max){ return false; } return ...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 输入描述: 输入一棵树 输出描述: 输出bool类型的数组,第一个是否是二叉搜索树,第二个是否是完全二叉树 示例 示例1 ...
  • 题目概述 解题思路 这道题的目标是,让我们找一棵搜索二叉树中,元素放错位置的两个节点的值。因为树中各个节点的值不相等,所以根据搜索二叉树的性质可知,这棵树(元素正确放置)的所有节点的中序遍历结果,一定是...
  • 本题来自左神《程序员代码面试指南》“找到二叉树中符合搜索二叉树条件的最大拓扑结构”题目。 题目 牛客OJ:找到二叉树中符合搜索二叉树条件的最大拓扑结构 给定一棵二叉树的头节点head,已知所有节点的值都不一样...
  • 二叉搜索树的中序遍历是一个升序序列,而交换其中两个节点后的遍历序列中可能会有两个逆序对,如(1,2,3,4,5)交换2和4(1,4,3,2,5),存在逆序对(4,3)和(3,2),第一个逆序对的第一个数个第二个逆序对的第二个数...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] import java.util.*; /* * public class TreeNode { * int val = ...
  • 本题来自左神《程序员代码面试指南》“调整搜索二叉树中两个错误的节点”题目。 原问题: 一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请找到这两个错误节点并返回...
  • 有序表和搜索二叉树

    2021-10-14 23:19:02
    搜索二叉树 定义:任何一个节点,左树都比这个节点小,右数都比这个节点大,经典搜索二叉树是没有重复值的,有重复值就压在一起 构造搜索二叉树方法: 比节点大,就往右边滑,滑到空就把节点加上 比节点小,就往...
  • 判断一棵二叉树是否为搜索二叉树和完全二叉树(C++牛客网)
  • 判断二叉树是否为搜索二叉树和完全二叉树 题目 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 解题思路 当前节点是完全二叉树条件: 左子树为完全二叉树 右子树也为完全...
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 输入 {2,1,3} 输出 [true,true] 备注: n≤500000 思路 判断二叉搜索树:中序遍历,每次比较当前节点p和前一个遍历到的...
  • 一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同) 示例1 输入 {1,2,3} 返回值 [1,2] 备注: 1 ...
  • 判断搜索二叉树和完全二叉树 题目描述 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 回顾: 搜索二叉树 二叉查找树(Binary ...
  • NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树 描述 给定一棵二叉树,已知其中的节点没有重复值,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入: {2,1,3} 复制 返回值: [true,true] import java....
  • 【说明】:本文是左程云老师所著的《程序员面试代码指南》第二章中“将搜索二叉树转换成双向链表”这一题目的C++复现。本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书...
  • 已知一个搜索二叉树后序遍历的数组posArr,根据posArr,重建整棵树并返回树的头结点。 基础知识: 搜索二叉树:(来源维基百科) 二叉查找树(英语:Binary Search Tree),也称为二叉查找树、有序二叉树(ordered ...
  • 牛客一题:找到搜索二叉树中两个错误的节点 今天分享一道在牛客网上的题目:找到搜索二叉树中两个错误的节点 结果,牛客网上面用例测试是通过的,反而显示没通过。 以此篇记 这一次的乌龙 各位朋友发现哪里有问题...
  • 2021-06-12:已知一棵搜索二叉树上没有重复值的节点,现在有一个数组arr,是这棵搜索二叉树先序遍历的结果。请根据arr生成整棵树并返回头节点。 福大大 答案2021-06-12: 先序遍历+中序遍历(搜索树)+不重复值=唯一...
  • 删除搜索二叉树中的结点 递归 没有孩子,直接删除 没左树,右树补;没右树,左树补 左右树都存在,左树补到右树最左结点的左边; 或右树补到左树最右结点的右边 class Solution { public: TreeNode* deleteNode...
  • 搜索二叉树

    2021-01-31 18:41:01
    搜索二叉树是一个特殊的二叉树 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点, 其左子树中所有结点的键值小于该结点的键值; 其右子树中所有结点的键值大于等于该结点的键值; 其左右子树都是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 115,418
精华内容 46,167
关键字:

搜索二叉树