DFS
Validate Binary Search Tree
Link: https://leetcode.com/problems/validate-binary-search-tree/
Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, null, null);
}
boolean validate(TreeNode node, Integer low, Integer high) {
// empty trees are valid
if (node == null) return true;
// current node's value must be between low and high.
if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
return false;
}
return validate(node.right, node.val, high) && validate(node.left, low, node.val);
}
}
Why parameter
low
andhigh
type is Integer instead of int?Because we need to pass null to the function
If we use int, we will get compile error.
Recover Binary Search Tree
Link: https://leetcode.com/problems/recover-binary-search-tree/
Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void inorder(TreeNode root, List < Integer > nums) {
if (root == null) return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}
public int[] findTwoSwapped(List < Integer > nums) {
int n = nums.size();
int x = -1, y = -1;
boolean swapped_first_occurrence = false;
for (int i = 0; i < n - 1; ++i) {
if (nums.get(i + 1) < nums.get(i)) {
y = nums.get(i + 1);
if (!swapped_first_occurrence) {
// first swap occurrence
x = nums.get(i);
swapped_first_occurrence = true;
} else {
// second swap occurrence
break;
}
}
}
return new int[] {
x,
y
};
}
public void recover(TreeNode r, int count, int x, int y) {
if (r != null) {
if (r.val == x || r.val == y) {
r.val = r.val == x ? y : x;
if (--count == 0) return;
}
recover(r.left, count, x, y);
recover(r.right, count, x, y);
}
}
public void recoverTree(TreeNode root) {
List < Integer > nums = new ArrayList();
inorder(root, nums);
int[] swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
}
The recursive inorder traversal approach:
class Solution {
TreeNode x = null, y = null, pred = null;
public void recoverTree(TreeNode root) {
findTwoSwapped(root);
swap(x, y);
}
void findTwoSwapped(TreeNode root) {
if (root == null) return;
findTwoSwapped(root.left);
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
else return;
}
pred = root;
findTwoSwapped(root.right);
}
void swap(TreeNode a, TreeNode b) {
int temp = a.val;
a.val = b.val;
b.val = temp;
}
}
Different DFS strategy:
Last updated