题解 | #牛群中的编号是否有效#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        // 使用中序遍历进行验证
        List<Integer> inorderList = new ArrayList<>();
        inorderTraversal(root, inorderList);

        // 检查中序遍历结果是否升序
        for (int i = 1; i < inorderList.size(); i++) {
            if (inorderList.get(i) <= inorderList.get(i - 1)) {
                return false;
            }
        }

        return true;
    }

    private void inorderTraversal(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.left, list);
        list.add(node.val);
        inorderTraversal(node.right, list);
    }
}

题目考察的知识点是：

二叉搜索树的性质以及如何验证一个二叉树是否为二叉搜索树。

解题方法分析：

1. 二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，对于每个节点，其左子树的所有节点都小于它，右子树的所有节点都大于它。这种性质可以通过中序遍历得到一个升序序列。
2. 要验证一个二叉树是否为二叉搜索树，可以利用中序遍历，然后检查遍历结果是否升序。如果升序，则满足二叉搜索树的性质。