【每日算法Day 29】二叉树基础4
二叉搜索树的验证、性质的利用，二叉树节点的祖先问题。
# LeetCode 98. 验证二叉搜索树 (opens new window)
# 题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
# 示例
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
2
3
4
5
6
7
8
9
# 解题思路
这一题的核心思想是，如果一个节点的两个子树是二叉搜索树并且该节点大于左子树中最大值、右子树的最小值，那么这个节点为根的树也是BST。那么这是个信息自底向上传递的场景，那么需要使用后序遍历。同时，传递的信息有三个：是否为BST、树中节点的最小值和最大值。最小值其实就是BST的最左节点的值，最大值为其最右节点的值。所以可以这样写：
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
if(root.left==null&&root.right==null) return true;
if(isValidBST(root.left)&&isValidBST(root.right)&&root.val>getMax(root.left)&&root.val<getMin(root.right)) return true;
return false;
}
private long getMin(TreeNode root) {
if (root==null) return Long.MAX_VALUE;
while (root.left != null) {
root=root.left;
}
return root.val;
}
private long getMax(TreeNode root) {
if (root==null) return Long.MIN_VALUE;
while (root.right != null) {
root=root.right;
}
return root.val;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
其中getMin和getMax对于空节点分别给出Long.MAX_VALUE和Long.MIN_VALUE，保证满足关系。不过使用这种方法每次都要查询子树的最大值和最小值，可以在递归遍历时使用Object[]数组封装要传递的信息：
public boolean isValidBST(TreeNode root) {
Object[] result=traversal(root);
return (Boolean) result[0];
}
private Object[] traversal(TreeNode root) {
//第二个数存贮树的最小值，第三个存最大值
Object[] info=new Object[3];
if (root == null) {
info[0]=true;
info[1]=Long.MAX_VALUE;
info[2]=Long.MIN_VALUE;
return info;
}
Object[] leftInfo=traversal(root.left);
Object[] rightInfo=traversal(root.right);
boolean b = (Boolean) leftInfo[0] && (Boolean) rightInfo[0] &&root.val>(Long)leftInfo[2]&&root.val<(Long)rightInfo[1];
info[0]=b;
info[1]=(Long) leftInfo[1]==Long.MAX_VALUE?root.val:(Long) leftInfo[1];
info[2]=(Long) rightInfo[2]==Long.MIN_VALUE?root.val:(Long) rightInfo[2];
return info;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
不过这种方式好像走偏了，LeetCode实际运行速度反而慢了1ms，各种类型强转也头皮发麻。。。看了下题解是可以从上到下传递约束信息的，每次传递给子节点其可以取值的上下界，如果不满足就返回false。并且使用null来判断封装类而不是直接比较大小更巧妙。
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
public boolean helper(TreeNode node, Integer lower, Integer upper) {
if (node == null) return true;
int val = node.val;
if (lower != null && val <= lower) return false;
if (upper != null && val >= upper) return false;
if (! helper(node.right, val, upper)) return false;
if (! helper(node.left, lower, val)) return false;
return true;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
此外，由于BST的中序遍历是严格递增的，可以对目标树进行非递归中序遍历，如果过程中发现某一值小于等于前面的值则返回false，遍历完都没有问题则返回true。
class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList();
long inorder = Long.MIN_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.val <= inorder) return false;
inorder = root.val;
root = root.right;
}
return true;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# LeetCode 235. 二叉搜索树的最近公共祖先 (opens new window)
# 题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先（一个节点也可以是它自己的祖先）。
# 示例
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
2
3
# 解题思路
这道题的关键在于：p 和 q 其中的一个在 LCA 节点的左子树上，另一个在 LCA 节点的右子树上。即一个值小于LCA的值，另一个值大于LCA的值(如果考虑节点本身可能就是LCA的话就是小于等于/大于等于)。那么从根节点开始搜索，只要不满足root.val >= low && root.val <= high就继续搜索，如果小于最小值则当前节点在p和q的“左侧”，root=root.right。反之亦然。这样第一个满足条件的点就是最近公共祖先。
迭代写法：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==null||p==null||q==null) return null;
int low=Math.min(p.val,q.val),high=Math.max(p.val,q.val);
while (!(root.val >= low && root.val <= high)) {
if (root.val>low)
root=root.left;
else
root=root.right;
}
return root;
}
2
3
4
5
6
7
8
9
10
11
递归写法：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int parentVal = root.val;
int pVal = p.val;
int qVal = q.val;
if (pVal > parentVal && qVal > parentVal) {
return lowestCommonAncestor(root.right, p, q);
} else if (pVal < parentVal && qVal < parentVal) {
return lowestCommonAncestor(root.left, p, q);
} else {
return root;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# LeetCode 236. 二叉树的最近公共祖先 (opens new window)
# 题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。该树不一定是BST。
# 解题思路
递归解法：
同上，两个节点的LCA一定满足：这两个节点分别在LCA的左右子树上。（考虑自身可能是LCA的话就是，LCA的值等于其中一个节点的值并且另一个节点在LCA的子树上）。只不过在BST中可以自上而下用值的大小来判断搜索范围，而这一题只能自下而上遍历来确认两个节点是否在当前节点的子树上。对于更早的祖先节点pq两点只会在其同一侧子树上所以会返回false。
TreeNode ancestor=null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
containsPQ(root,p.val,q.val);
return ancestor;
}
private boolean containsPQ(TreeNode root,int p,int q) {
if (root==null) return false;
boolean leftContains=containsPQ(root.left,p,q);
boolean rightContains=containsPQ(root.right,p,q);
if ((leftContains && rightContains) || ((root.val == p || root.val == q) && (leftContains || rightContains))) {
ancestor=root;
}
return leftContains||rightContains||root.val==p||root.val==q;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
迭代解法： 我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set<Integer> visited = new HashSet<Integer>();
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {
return q;
}
q = parent.get(q.val);
}
return null;
}
}
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