
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        preorder(root,list);
        return list;
    }
    private void preorder(TreeNode root,List<Integer>list){
        if(root==null){
            return;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

中序

https://leetcode.cn/problems/binary-tree-inorder-traversal/


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

后序

https://leetcode.cn/problems/binary-tree-postorder-traversal/


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

2.前中后序遍历（迭代）

先整体写出遍历的顺序，然后再根据前中后序的顺序，确定添加到List的时机。三种遍历统一可以使用一个模版


class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 设置一个数组用来保存二叉树前序遍历的结果
        List<Integer> preorderResult=new ArrayList<>();
 
        // 设置一个数组用来保存二叉树中序遍历的结果
        //List<Integer> inorderResult = new ArrayList<>();
        // 设置一个数组用来保存二叉树后序遍历的结果
        //List<Integer> postorderResult = new ArrayList<>();
 
         // 设置一个栈，用来保存路径
        Stack<TreeNode> stack=new Stack<>();
         // 左代表该节点的左右孩子节点都没有遍历
        int nodeLeft=1;
         // 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历
        int nodeRight=2;
         // 上代表左右孩子节点都已经遍历，需要返回到它的父节点
        int nodeUp=3;
        // 每个节点的初始化状态都是从左开始
        int nodeState=nodeLeft;
        TreeNode node=root;
 
        while(node!=null){
           
            if(nodeState==nodeLeft){
                preorderResult.add(node.val);
                if(node.left!=null){
                    stack.push(node);
                    node=node.left;
                }else{
                    nodeState=nodeRight;
                }
            }else if(nodeState==nodeRight){
 
               // 把当前节点加入到二叉树中序遍历的结果数组中
               // inorderResult.add(node.val);
 
                if(node.right!=null){
                    stack.push(node);
                    node=node.right;
                    nodeState=nodeLeft;
                }else{
                    nodeState=nodeUp;
                }
            }else if(nodeState==nodeUp){
               
               // 把当前节点加入到二叉树后序遍历的结果数组中
               //postorderResult.add(node.val);
 
                TreeNode parent=null;
                if(!stack.isEmpty()){
                    parent=stack.pop();
 
                    if(parent.left==node){
                    nodeState=nodeRight;
                }
                }
                node=parent;
            }
        }
        return preorderResult;
     }
}

3.翻转二叉树（LeetCode 226）

https://leetcode.cn/problems/invert-binary-tree/description/

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]


class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        if(root.left==null && root.right==null){
            return root;
        }
        TreeNode left=invertTree(root.left);
        TreeNode right=invertTree(root.right);
 
        root.left=right;
        root.right=left;
        return root;
    }
}


class Solution {
    public TreeNode invertTree(TreeNode root) {
 
        // 1、递归终止条件一，当前节点为空的时候，就返回 null
        if(root == null) return null;
 
        // 2、递归终止条件二，当前节点为叶子节点的时候，就返回这个节点
        if( root.left == null && root.right == null){
            
            // 返回这个节点
            return root;
 
        }
 
        // 3、把当前这个节点 root 的左子树进行翻转操作
        TreeNode left =  invertTree(root.left);
 
        // 4、把当前这个节点 root 的右子树进行翻转操作
        TreeNode right = invertTree(root.right);
 
        // 5、把翻转成功的右子树赋值给 root 的左子树
        root.left = right;
 
        // 6、把翻转成功的左子树赋值给 root 的右子树
        root.right = left;
 
        // 7、返回翻转成功的二叉树的根节点
        return root;
 
    }
}

4.最大二叉树（ LeetCode 654 ）

https://leetcode.cn/problems/maximum-binary-tree/description/

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。


class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
       return maxBinaryTreeNode(nums,0,nums.length-1);
    }
 
    private TreeNode maxBinaryTreeNode(int[]nums,int left,int right){
        if(left>right){
            return null;
        }
        if(left==right){
            return new TreeNode(nums[left]);
        }
        int maxIndex=left;
        for(int i=left+1;i<right+1;i++){
            if(nums[i]>nums[maxIndex]){
                maxIndex=i;
            }
        }
        TreeNode root=new TreeNode(nums[maxIndex]);
        TreeNode leftNode=maxBinaryTreeNode(nums,left,maxIndex-1);
        TreeNode rightNode=maxBinaryTreeNode(nums,maxIndex+1,right);
        root.left=leftNode;
        root.right=rightNode;
        return root;
    }
}

5.平衡二叉树（ LeetCode 110 ）

https://leetcode.cn/problems/balanced-binary-tree/

给定一个二叉树，判断它是否是

平衡二叉树:每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false


class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root)!=-1;
    }
    private int recur(TreeNode curNode){
        if(curNode==null){
            return 0;
        }
        int left=recur(curNode.left);
        if(left==-1) return -1;
        int right=recur(curNode.right);
        if(right==-1) return -1;
 
        return Math.abs(left-right)<2 ? Math.max(left,right)+1:-1;
    }
}


class Solution {
    public boolean isBalanced(TreeNode root) {
         // 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
        return recur(root) != -1;
    }
 
    private int recur(TreeNode curNode) {
        
        // 递归终止条件
        // 如果当前节点 curNode 为空，那么高度就是 0
        if (curNode == null) return 0;
 
        // 递归的计算当前节点 curNode 的左子树高度
        int left = recur(curNode.left);
 
        // 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(left == -1) return -1;
 
        // 递归的计算当前节点 curNode 的右子树高度
        int right = recur(curNode.right);
 
        // 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
        // 提前终止了后续的判断
        if(right == -1) return -1;
 
        // 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
        // 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
        // 因此计算一下当前节点 curNode 是否是平衡二叉树
        // 即计算 curNode 的左子树高度与右子树高度差
        // 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
        // 即节点 curNode 的左右子树中最大高度加 1 
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

6.二叉树的最小深度（ LeetCode 111 ）

即为求最短路径

https://leetcode.cn/problems/minimum-depth-of-binary-tree/


class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> nodeTree=new LinkedList<>();
        if(root==null){
            return 0;
        }
        nodeTree.add(root);
        int depth=0;
        while(nodeTree!=null){
            int size=nodeTree.size();
            depth++;
            for(int i=0;i<size;i++){
                TreeNode node=nodeTree.poll();
                if(node.left==null && node.right==null){
                    return depth;
                }
                if(node.left!=null){
                    nodeTree.add(node.left);
                }
                if(node.right!=null){
                    nodeTree.add(node.right);
                }
            }
        }
        return depth;
    }
}

来一个趴菜现在才知道的知识点。。。虽然此题判断条件中queue != null 和 !queue.isEmpty() 都不会报错。。。

!queue.isEmpty()更准确，queue != null不报错是因为上面有添加root，对queue已经有初始化了。

queue != null 和 !queue.isEmpty() 是两个用于不同目的的检查，它们在代码中的使用情况和意图有所不同。
queue != null 是用来确认队列对象是否已经初始化。它主要用于确保代码在访问队列之前不会引发 NullPointerException。
!queue.isEmpty() 是用来检查队列是否有元素。在尝试访问或操作队列的元素之前进行检查，以确保队列中有数据可以处理。
通常，这两个检查是相辅相成的。在处理队列时，首先需要确认队列对象本身是有效的 (queue != null)，然后检查队列是否包含元素 (!queue.isEmpty())。


class Solution {
    public int minDepth(TreeNode root) {
        // 边界情况处理
        if (root == null) return 0;
 
        // 设置一个队列，用来存储二叉树中的元素
        Queue<TreeNode> nodeQueue = new LinkedList<>();
 
        // 队列添加二叉树的根节点
        nodeQueue.add(root);
 
        // 设置 depth 用来保存输出结果
        int depth = 0;
 
        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while (!nodeQueue.isEmpty()) {
 
            // 用来记录 queue 的长度，即每层节点的个数
            int size = nodeQueue.size();
 
            // 每到一层，深度就 +1
            depth++;
 
            // 使用 for 循环，将 nodeQueue 中的元素统计
            for (int i = 0; i < size; i++) {
 
                // 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点      
                TreeNode curNode = nodeQueue.poll();
 
                // curNode.left == null && curNode.right == null 
                // 说明是叶子结点
                // 由于【最小深度是从根节点到最近叶子节点的最短路径上的节点数量】
                // 直接返回 depth 
                if(curNode.left == null && curNode.right == null){
                    return depth;
                }
 
                // 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if (curNode.left != null){
                    nodeQueue.add(curNode.left);
                } 
 
                // 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if (curNode.right != null){
                    nodeQueue.add(curNode.right);
                }
 
            }
        }
 
        // 返回 depth
        return depth;
    }
}

7.二叉树的最大深度（ LeetCode 104 ）

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。


class Solution {
    public int maxDepth(TreeNode root) {
 
        // 如果 root 为空，直接返回 0
        if(root == null) return 0;
 
        // 递归调用 maxDepth，求出当前节点的左子树的最大深度
        int left = maxDepth(root.left);
 
        // 递归调用 maxDepth，求出当前节点的右子树的最大深度
        int right = maxDepth(root.right);
 
        // 求出当前节点的左右子树中较大的值
        int childMaxDepth = Math.max(left,right);
 
        // 二叉树的最大深度就是它的左右子树中较大的值加上 1
        return childMaxDepth + 1;
    }
}

8.二叉树的最近公共祖先（ LeetCode 236 ）（重点）

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”


class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root==p) return p;
        if(root==q)  return q;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null && right==null){
            return null;
        }else if(left==null){
            return right;
        }else if(right==null){
            return left;
        }else{
            return root;
        }
    }
}


class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 
        // 1、如果此时访问的节点 root 为 null，那么直接返回 null
        if(root == null ) return null;
 
        // 2、如果此时访问的节点 root 为指定节点 p，那么返回 p 这个节点
        if(root == p)  return p;
 
        // 3、如果此时访问的节点 root 为指定节点 q，那么返回 q 这个节点
        if(root == q) return q;
        
        // 4、经过上面 1、2、3 的判断之后，root 这个节点必然不是 p、q、null 这三种情况的节点
        // 接下来，去递归的判断当前节点 root 的左右子树是否包含 p 、q 这两个指定节点
 
 
        // 5、递归的去查找 root 的左子树，判断是否包含p 、q 这两个指定节点
        // 如果 root 的左子树节点和它的左子树所有节点中包含 p，那么 left 的值就是 p
        // 如果 root 的左子树节点和它的左子树所有节点中包含 q，那么 left 的值就是 q
        // 如果 root 的左子树节点和它的左子树所有节点中既不包含 p，也不包含 q，那么 left 的值就是 null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
 
 
        // 6、递归的去查找 root 的右子树，判断是否包含p 、q 这两个指定节点
        // 如果 root 的右子树节点和它的右子树所有节点中包含 p，那么 right 的值就是 p
        // 如果 root 的右子树节点和它的右子树所有节点中包含 q，那么 right 的值就是 q
        // 如果 root 的右子树节点和它的右子树所有节点中既不包含 p，也不包含 q，那么 right 的值就是 null
        TreeNode right = lowestCommonAncestor(root.right, p, q);
 
 
        // 7、判断完当前节点 root 、 root 的左子树 left、root 的右子树 right 的情况后
        // 开始向父节点传递信息
 
        // 8、如果 root 节点的左子树 left 和右子树 right 都没有找到指定节点 p、q
        // 并且 root 自己本身也不是指定节点 p、q
        // 那么它给父节点传递的信息就是以 root 为根节点的那颗二叉树没有指定节点 p、q 
        if(left == null && right == null){
 
            // 返回 null，告诉 root 的父节点，这里没找到指定节点 p、q
            return null;
 
        // 9、如果在 root 节点的左子树 left 中没有找到指定节点 p、q 
        // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 right 了
        }else if(left == null){
 
            // 返回 right ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 right 
            return right;
 
        // 10、如果在 root 节点的右子树 right 中没有找到指定节点 p、q 
        // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 left 了
        }else if(right == null){
 
            // 返回 left ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 left 
            return left;
 
        // 11、此时，left != null 并且 right != null
        // 这说明在以 root 节点为根节点的那棵二叉树中找到了指定节点 p ，也找到了指定节点 q 
        // 那么就告诉父节点，root 就是 p、q 的最近公共祖先
        }else{
 
            // 返回 root ，告诉 root 的父节点，root 就是 p、q 的最近公共祖先
            return root;
        } 
    }
}

9.从前序与中序遍历序列构造二叉树（ LeetCode 105 ）（重点）

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/


class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        TreeNode root=new TreeNode(preorder[0]);
        for(int i=1;i<preorder.length;i++){
            TreeNode node=new TreeNode(preorder[i]);
            insert(root,node,map);
        }
        return root;
    }
 
    private void insert(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){
        while(node!=root){
            if(map.get(node.val)<map.get(root.val)){ 
                if(root.left==null){
                    root.left=node;
                }
                root=root.left;
            }else{
                if(root.right==null){
                    root.right=node;
                }
                root=root.right;
            }
        }
    }
}


class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
 
        // 题目中说 preorder 和 inorder 均无重复元素
        // 通过哈希表把中序遍历序列中的值和顺序建立映射关系
        HashMap<Integer, Integer> map = new HashMap<>();
 
        // 通过 for 循环，遍历完中序遍历序列中的所有元素
        for (int i = 0; i < inorder.length; i++) {
             // 以中序序列中的元素值 inorder[i] 作为 key
             // 以位置 i 作为 value
             // 存放到哈希表中
             // 比如中序遍历序列中的元素是 [   A  ,   D  ,   E  ,   F  ,   G  ,   H  ,   M  ,   Z  ]
             // 那么这个哈希表就是以下的样子
             // | 索引 | 位置  |
             // | A | 0  |
             // | D | 1  |
             // | E | 2  | 
             // | F | 3  | 
             // | G | 4  | 
             // | H | 5  | 
             // | M | 6  | 
             // | Z | 7  |            
             map.put(inorder[i], i);
        }
 
        // 下面开始构建二叉树
        // 把前序遍历序列中的第一个元素 preorder[0] 作为二叉树的根节点
        // 因为任意二叉树的前序遍历序列中的第一个元素，一定是二叉树的根节点
        TreeNode root = new TreeNode(preorder[0]);
 
 
        // 继续遍历前序遍历序列中的其它元素
        for(int i = 1 ; i < preorder.length ; i++){
 
            // 把当前遍历的元素构造为一个二叉树的节点
            TreeNode node = new TreeNode(preorder[i]);
 
            // 把构造的节点插入到以 root 为根节点的二叉树中
            insertNode(root,node,map);
 
        }
 
        // 当 preorder 中所有元素都构造并且插入完毕之后
        // 二叉树就完成了构建
        return root;
 
 
    }
 
    // root : 二叉树的根节点
    // node : 待插入的节点
    // map : 节点值和中序遍历序列位置的映射
    private void insertNode(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){
 
            // 当 root 和 node 指向的节点相同时，跳出循环
            while(root != node){
 
                // 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
                // 说明 node 应该在 root 的左子树中
                if(map.get(node.val) < map.get(root.val)){
 
                    // 如果此时 root 没有左子树
                    if(root.left == null){
                        // 那么就把 node 设置为 root 的左子树
                        root.left = node;
                    }
 
                    // 1、如果之前 root 没有左子树，那么通过上面的代码，就设置好了 root 的左子树
                    // 也就是说 node 是 root 的一个叶子节点，完成了插入操作
                    // 把 root 指向 root.left 后，root 为 node，跳出了循环
 
                    // 2、如果之前 root 已经有左子树，那么就不能直接把 node 插入到 root 的左子树上
                    // 需要判断应该把 node 插入到 root 左子树上的孩子节点的那个位置上
                    // 比如现在的 root 是这个样子，node 为 A
                    //        G
                    //       /
                    //      D
                    //     /  \
                    //    ①   ②
                    // root 已经有左子树 D 了，所以 node 应该考虑插入到 D 中的 ① 还是 ② 上面
                    // 所以，把 root 指向 root.left ，继续遍历 root 的左子树的情况
                    root = root.left;
 
                    
                }else{
 
                    // 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
                    // 说明 node 应该在 root 的右子树中
                    
                    // 如果此时 root 没有右子树
                    if(root.right == null){
                        // 那么就把 node 设置为 root 的右子树
                        root.right = node;
                    }
 
                    // 把 root 指向 root.right ，继续遍历 root 的右子树的情况
                    root = root.right;
                    
                }
 
            }
    }
}

10.从中序与后序遍历序列构造二叉树（ LeetCode 106 ）

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

与上面前中构造基本一致，不同的是后序数组从后往前遍历，后序数组的最后一个值，为整棵树的根节点。


class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        TreeNode root=new TreeNode(postorder[postorder.length-1]);
        for(int i=postorder.length-2;i>=0;i--){
            TreeNode node=new TreeNode(postorder[i]);
            insert(root,node,map);
        }
        return root;
    }
 
    private void insert(TreeNode root,TreeNode node,HashMap<Integer,Integer> map){
        while(node!=root){
            if(map.get(node.val)<map.get(root.val)){ 
                if(root.left==null){
                    root.left=node;
                }
                root=root.left;
            }else{
                if(root.right==null){
                    root.right=node;
                }
                root=root.right;
            }
        }
    }
}

11.合并二叉树（LeetCode 617）

https://leetcode.cn/problems/merge-two-binary-trees/description/

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。


class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
           if(root1==null && root2==null){
            return null;
           }
           if(root1==null){
            return root2;
           }
           if(root2==null){
            return root1;
           }
           TreeNode mergeNode=new TreeNode(root1.val+root2.val);
           mergeNode.left=mergeTrees(root1.left,root2.left);
           mergeNode.right=mergeTrees(root1.right,root2.right);
           return mergeNode;
    }
}

12.验证二叉搜索树（LeedCode 98）

https://leetcode.cn/problems/validate-binary-search-tree/

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

解法一：中序遍历+比较数组是否单调递增


//二叉搜索树的中序遍历，节点的值一定是单调递增的
 //将二叉搜索树的中序遍历的值存放在数组中
 //判断这个数组是否是单调递增的
class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inorderTree(root,list);
        return isCreasing(list);
    }
 
    private void inorderTree(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        inorderTree(root.left,list);
        list.add(root.val);
        inorderTree(root.right,list);
    }
 
    private boolean isCreasing(List<Integer> list){
        for(int i=1;i<list.size();i++){
            if(list.get(i)<=list.get(i-1)){
                return false;
            }
        }
        return true;
    }
}

解法二：中序遍历+双指针

相比上种方法，少了一步存放各个节点的值。在中序遍历的过程中，每次比较当前应该节点和当前节点的大小即可。


class Solution {
    public boolean isValidBST(TreeNode root) {
        return inorderTree(root);
   }
   //如果当前节点为空，则返回 true。这是递归的终止条件，也表明空节点是有效的 BST。
   TreeNode pre=null;
 
   private boolean inorderTree(TreeNode root){
    if(root==null){
        return true;
    }
    //首先递归遍历当前节点的左子树。如果左子树不符合 BST 的条件（返回 false），则当前树也不符合 BST 的条件，返回 false。
    if(!inorderTree(root.left)){
        return false;
    }
    //prev != null：确保 prev 已经被初始化，检查当前节点值 node.val 是否大于前一个节点的值prev.val
    if(pre!=null && root.val<=pre.val){
        return false;
    }
 
    //更新 prev 为当前节点，以便在接下来的遍历中进行比较
    pre=root;
    //遍历当前节点的右子树。如果右子树不符合 BST 的条件（返回 false），则返回 false；否则，返回 true
    return inorderTree(root.right);
   }
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/1021272