【剑指Offer+LeetCode-98】判断一颗满二叉树是否是二叉搜索树 + 验证二叉搜索树_判断一个 二叉树 是不是满二叉树 leetcode

【剑指Offer】判断一颗满二叉树是否是二叉搜索树

题目描述

给定一棵满二叉树，判定该树是否为二叉搜索树，是的话打印True，不是的话打印False

说明：
a. 二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

b. 满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树

c. 树内节点数不超过 10000，非空节点值为大于0小于65536的整数，空树或空节点输入为None

输入描述:
从根节点开始，逐层输入每个节点的值，空树或空节点输入为None
比如：10,5,15,3,7,13,18

输出描述:
是二叉搜索树的话打印True，不是的话打印False

示例1
输入
10,5,15,3,7,13,18

输出
True

解题思路一：

根据满二叉树的特征创建二叉树：

        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        if (s1.equals("None")) {
            System.out.println("True");
            return;
        }
        String[] s = s1.split(",");
        //数组a保存满二叉树的层次遍历节点顺序
        TreeNode []a = new TreeNode[s.length];
        for (int i = 0; i < s.length; i++) {
            int val = Integer.parseInt(s[i]);
            a[i] = new TreeNode(val);
        }

        //根据满二叉树的层次遍历顺序创建满二叉树：利用满二叉树父节点与左右节点之间的序号关系
        //将节点数组中的每个结点相连
        for (int i = 0; i < a.length; i++) {
            if (2 * i + 1 < a.length) {
                a[i].left = a[2 * i + 1];
            }
            if (2 * i + 2 < a.length) {
                a[i].right = a[2 * i + 2];
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

测试通过完整代码：

import java.util.Scanner;

//定义树结点
class TreeNode{
    int val;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode(int val){
        this.val = val;
    }
}

public class Main {

    //lastVal保存中序遍历上一个节点值(因为二叉查找树的中序遍历递增，上一个节点值一定大于当前访问的节点值)
    private static int lastVal = Integer.MIN_VALUE;

    // 方法1、使用中序遍历判断二叉查找树（保存中序遍历上一个节点值）
    public static boolean judgeBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        //先递归访问当前节点的左子树
        if (!judgeBST(root.left)) {
            return false;
        }
        //访问当前根节点，要求当前根节点的值要大于上一次访问的节点值（即在当前根节点的左子树上）
        if (root.val <= lastVal) {
            return false;
        }
        //访问当前节点的右子树之前，需要更新lastVal
        lastVal = root.val;
        if (!judgeBST(root.right)) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        if (s1.equals("None")) {
            System.out.println("True");
            return;
        }
        String[] s = s1.split(",");
        //数组a保存满二叉树的层次遍历节点顺序
        TreeNode []a = new TreeNode[s.length];
        for (int i = 0; i < s.length; i++) {
            int val = Integer.parseInt(s[i]);
            a[i] = new TreeNode(val);
        }

        //根据满二叉树的层次遍历顺序创建满二叉树：利用满二叉树父节点与左右节点之间的序号关系
        //将节点数组中的每个结点相连
        for (int i = 0; i < a.length; i++) {
            if (2 * i + 1 < a.length) {
                a[i].left = a[2 * i + 1];
            }
            if (2 * i + 2 < a.length) {
                a[i].right = a[2 * i + 2];
            }
        }

        //根节点为数组a的第一个节点
        TreeNode root = a[0];


        //注意错误的方法，但是本题运行可以通过90%测试用例：（这种方法只能判断局部二叉搜索树，不能判断全局）：二叉搜索树的左子树节点值 < 根节点 < 右子树（
        //正确的方法：判断该满二叉树是否是二叉搜索树
        //方法1、使用中序遍历判断二叉查找树（保存中序遍历上一个节点值）
        if (judgeBST(root)) {
            System.out.println("True");
        }else {
            System.out.println("False");
        }

    }
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

【LeetCode-98】判断一颗二叉树是否是二叉搜索树（验证二叉搜索树）

扩展：使用中序遍历判断二叉查找树（保存到数组中）

根据二叉查找树的性质我们可以知道：如果我们用中序遍历遍历二叉查找树的话，遍历到的每个节点是依次增大的。

根据这个思路，我们可以遍历一遍树，将遍历到的值保存到数组中，然后再判断这个数组是否为递增数组就可以了。下面是算法片段：

List<Integer> list=new ArrayLIst<>();
public void isTree(TreeNode root){
    if(root == NULL)  return;
    isTree(root.left);
    list.add(root.val);
    isTree(root.right);
}
public static void main(String[] args){
    //假设给定了树的根节点root
    isTree(root);
    for(int i = 1; i < list.size(); i++)
        if(list.get(i-1) >= list.get(i]))
            return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

扩展：使用中序遍历判断二叉查找树（保存中序遍历上一个节点值）

1、使用 O(1) 的空间复杂度

• 方法：只保存遍历节点的上一个节点值，不需要另外开辟空间。因为中序遍历是递增的，所以只需要比较上一个节点值和该节点值的大小即可。

递归算法思路就是如下：

int last = Integer.MIN_VALUE;
public boolean isTree(TreeNode root){
    if(root == null)    
        return true;
    if(!isTree(root.left))    
        return false;
    if(root.val <= last)    
        return false;
    last=root.val;
    if(！isTree(root.right))    
        return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、迭代算法实现

思路：使用栈进行存储，先将左子树压入栈，然后依次取出判断。

代码如下：

public boolean isBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode p = root, pre = null;
    while(p != null || !stack.isEmpty()){
        while(p != null){
            stack.push(p);
            p = p.left;
        }         
        TreeNode t = stack.pop();
        if(pre != null && t.val <= pre.val)
            return false;
        pre = t;
        p = t.right;        
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

扩展：使用Morris Traversal方法判断一颗树是否是二叉查找树

• 不用栈存储

• 空间复杂度为O(1)

• 思路：利用叶子节点中的左、右空指针指向中序遍历下的前驱节点或后继节点，从而得到判断条件。

  在一开始last，用的是int last=Ineger.MIN_VALUE ，结果在leetcode上跑的时候有个测试用例是 -2147483648，正好是MIN_VALUE，然后就判断错误，于是用了其包装类型。

代码如下：

public boolean isValidBST(TreeNode root) {
    if(root == null) 
        return true;
    Integer last = null;
    TreeNode cur=root, pre=null;
    while(cur != null){
        if(cur.left != null){
            pre = cur.left;
            while(pre.right != null && pre.right != cur)
                pre = pre.right;
            if(pre.right == null){
                pre.right = cur;
                cur = cur.left;
            }else{
                pre.right = null;
                if(last != null && cur.val <= last)
                    return false;
                last = cur.val;
                cur = cur.right;
            }                                                   
        }else{
            if(last != null && cur.val <= last)
                return false;
            last = cur.val;
            cur = cur.right;
        }
    }
    return true;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

扩展：用每个子树的最大最小值和根节点值比较得到结果

参考文章：
https://blog.csdn.net/xiaoweiba_h/article/details/81836804

递归非递归方法
https://blog.csdn.net/qq_30490125/article/details/53135274

Morris Traversal方法
https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
Leetcode上题目
https://leetcode-cn.com/problems/validate-binary-search-tree