Java 求解验证二叉搜索树

逃离我推掉我的手 2022-10-17 01:58 196阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、题解
     *  三、递归法
     *  四、迭代法
     *  五、总结

## 一、题目 ##

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、题解 ##

题目判断该树是否是二叉搜索树

利用二叉搜索树的性质，对其进行中序遍历，判断是否递增即可

## 三、递归法 ##

class Solution { 
        //pre 用来记录前一个节点
        //需要设置为全局变量，每次和前一个量比较
        TreeNode pre = null;
    
        public boolean isValidBST(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            boolean left = isValidBST(root.left);
            if (pre != null && pre.val >= root.val) { 
                return false;
            }
            //记录前一个节点
            pre = root;
            boolean right = isValidBST(root.right);
            return left && right;
        }
    }

## 四、迭代法 ##

关键是非递归实现中序遍历，同时使用前驱 pre 记录上一个值，和当前值进行比较

class Solution { 
        public boolean isValidBST(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            //记录前一个节点
            TreeNode pre = null;
            while (!deque.isEmpty() || root != null) { 
                if (root != null) { 
                    deque.push(root);
                    root = root.left;
                } else { 
                    root = deque.pop();
                    //中序遍历，判断是否递增
                    if (pre != null && pre.val >= root.val) { 
                        return false;
                    }
                    pre = root;
                    root = root.right;
                }
            }
            return true;
        }
    }

## 五、总结 ##

该题主要是对，中序遍历的应用：

**中序递归遍历：**

class Solution { 
        List<Integer> list = new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) { 
            if(root==null){ 
                return list;
            }
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
            return list;
        }
    }

**中序非递归遍历：** 注意这里和前序和后序的区别，指针表示了节点访问，root 根节点 while 循环内才放入 deque

class Solution { 
        List<Integer> list = new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) { 
            if (root == null) { 
                return list;
            }
            //中序遍历依靠栈处理节点
            Deque<TreeNode> deque = new LinkedList<>();
            //指针用于访问节点
            TreeNode cur = root;
            while (cur != null || !deque.isEmpty()) { 
                //遍历节点到最底层
                if (cur != null) { 
                    deque.push(cur);
                    cur = cur.left;
                } else { 
                    cur = deque.pop();
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
            return list;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221014/ca545df7893949a7be49f58166feb237.png