# 算法：树和图-实战

leetcode:98. 验证二叉搜索树

### 递归

```class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isValidBST(TreeNode root) {
return recursive(root, null, null);
}

public Boolean recursive(TreeNode node, Integer leftMax, Integer rightMin) {
if (node == null) return true;
// 正常应该小于最大值，大于最小值.其实也不应该说是最大最小值，这只是一个参考。
if (rightMin != null && node.val <= rightMin) return false;
if (leftMax != null && node.val >= leftMax) return false;

if(!recursive(node.right, leftMax,node.val)) return false; //设最小值为root/父亲节点（node），右子树都大于最小值，
if (!recursive(node.left, node.val, rightMin)) return false;//设最大值为root/父亲节点，左子树都小于最大值
return true;
}
}

//不通过最大最小值的递归
/**
class Solution {
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
if(!isValidBST(root.left)) return false;
if(pre != null && pre.val >= root.val) return false;
pre = root;
return isValidBST(root.right);
}
}
*/```

### 中序遍历

```class Solution13 {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null|| !stack.isEmpty()) {
while (root != null ) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && pre.val >= root.val) return false;
pre = root;
root = root.right;
}
return true;
}
}```

## leetcode:236二叉树最近的公共祖先

### 递归

```public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;//递归出口
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//        也可以用三目表达式
//        return left == null ? right : right == null ? left : root;
if (left != null && right != null) {
return root;
} else if (left != null && right == null) {
return left;
} else if (left == null && right != null) {
return right;
}
return null;
}```

## leetcode:235二叉搜索树最近的公共祖先

### 递归

```public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,  p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}```

### 遍历

```    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (root.val > p.val && root.val > q.val) root = root.left;
else if (root.val < p.val && root.val < q.val) root = root.right;
else return root;
}
return root;
}```

0 条评论

• ### 算法：递归和分治-理论

一说起循环，大家都会说一个例子：“从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山...” 这...

• ### 腾讯云服务器Linux系统--安装Oracle JDK

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 腾讯云服务器Linux系统--安装Tomcat

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### Leetcode 653. Two Sum IV - Input is a BST

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.cs...

• ### 【leetcode刷题】T112-验证二叉搜索树

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

• ### LintCode Binary Tree Maximum Node二叉树的最大节点分析代码

Find the maximum node in a binary tree, return the node.

• ### Leetcode【700、872、897、965、1022】

1、判断叶子的条件是 root.left == None and root.right == None，返回 [root.val]； 2、还要注意单子树的情况...

• ### 14.4 exportfs命令

exportfs命令 常用选项 -a 全部挂载或者全部卸载 -r 重新挂载 -u 卸载某一个目录 -v 显示共享目录 以下操作在服务端上 -vim /etc/e...

• ### 天天算法 LeetCode-938-二叉搜索树的范围和

https://leetcode-cn.com/problems/range-sum-of-bst/