专栏首页营琪的小记录算法:树和图-实战

算法:树和图-实战

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

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...

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

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

    木又AI帮
  • LintCode Binary Tree Maximum Node二叉树的最大节点分析代码

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

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

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

    echobingo
  • 14.4 exportfs命令

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

    运维小白
  • 天天算法 LeetCode-938-二叉搜索树的范围和

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

    灵魂画师牧码
  • 2 服务器基本情况

    Y大宽

扫码关注云+社区

领取腾讯云代金券