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

考察线索二叉树的结构判断，二叉树的知识点都会用到递归算法。

递归算法需要找到递归出口。所以节点为null的时候就可以返回true了，随后判断其左右子节点的值是否满足线索二叉树的要求。均满足之后向下递归判断其左右子树是否满足线索二叉树的定义，最终判断整个树的结构。

Java代码如下所示

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
        if(root==null) return true;
        if(root.left!=null){
            if(root.val<=root.left.val) return false;
        }
        if(root.right!=null){
            if(root.val>=root.right.val) return false;
        }
        return isValidBST(root.left)&&isValidBST(root.right);
    }
}