• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

面试题 04.05. 合法二叉搜索树

开发技术 开发技术 2周前 (04-29) 5次浏览

实现一个函数,检查一棵二叉树是否为二叉搜索树。

示例 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);
    }
}

 

 



程序员灯塔
转载请注明原文链接:面试题 04.05. 合法二叉搜索树
喜欢 (0)