Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Solution 1: For each sub-tree, we maintain its lower bound and upper bound. The tricky part is to deal with the maximum integer and the minimum integer. In the following Java code, I used two additional flags to denote whether the lower bound is -infty and whether the upper bound is +infty, respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST( TreeNode root, int lower_bound, int upper_bound, boolean neg_infty, boolean pos_infty ) { if (root == null) return true; if (root.val <= lower_bound && !neg_infty) return false; if (root.val >= upper_bound && !pos_infty) return false; return isValidBST(root.left, lower_bound, root.val, neg_infty, false) && isValidBST(root.right, root.val, upper_bound, false, pos_infty); } public boolean isValidBST(TreeNode root) { return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE, true, true); } } |
Solution 2: In-order traversal. The resulting list should be in the increasing order. Simple, yet it uses additional space.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if (root == null) return list; list.addAll(inorderTraversal(root.left)); list.add(root.val); list.addAll(inorderTraversal(root.right)); return list; } public boolean isValidBST(TreeNode root) { if (root == null) return true; ArrayList<Integer> list = inorderTraversal(root); for (int i = 1; i < list.size(); i++) { if (list.get(i-1) >= list.get(i)) { return false; } } return true; } } |
No comments:
Post a Comment