实现一个函数,检查一棵二叉树是否为二叉搜索树。
示例 1:
输入: 2 / \ 1 3 输出: true
示例 2:
输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。
简单好理解的做法:
中序遍历。后放入list中。克隆list, 排序list,如果list,和clone中的对象 相同位置元素 不相等就不合法,全部相等就合法。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { ArrayList<Integer> list = new ArrayList<>(); public boolean isValidBST(TreeNode root) { helper(root); //中序后,正确的结果是从小到大的排序,否则list中有乱序就是错的. ArrayList<Integer> clone = (ArrayList<Integer>) list.clone(); Collections.sort(list); for(int i = 0; i< list.size();i++) { int a = list.get(i); int b = clone.get(i); if(a!=b) return false; } return true; } public void helper(TreeNode root) { if(root == null) return ; helper(root.left); list.add(root.val); helper(root.right); } }