算法：树和图-实战

营琪

发布于 2019-11-04 16:49:30

6750

发布于 2019-11-04 16:49:30

文章被收录于专栏：营琪的小记录营琪的小记录

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二叉树最近的公共祖先

递归

思路：找两个节点的公共祖先节点，也就是搜索二叉树找某一个值，并把路径保存下来，两条路径重叠的部分，也就是公共祖先节点了。

再简化一点就是，同时在node节点的左右进行查找，对node的节点递归，递归的返回值是否存在，也就代表着当前节点是否公共祖先节点。

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;
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-08-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树