二叉树的深搜

用户11369558

发布于 2024-11-20 15:07:25

1960

文章被收录于专栏：JavaJava

前言：本章节更深入学习递归

计算布尔二叉树的值

思路： 1.函数头设计：dfs（root） 2.函数体：需要一个接收left 和 right 的值并且根据root的值进行比较 3.递归出口：很明显当为叶子节点的时候向上返回你叶子节点的值并且与当前root的值进行比较

    public boolean evaluateTree(TreeNode root) {
        if(root.left == null && root.right == null) {
            return root.val > 0;
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left || right : left && right;
    }

求根节点到叶节点数字之和

从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

    int ret = 0;

    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int preSum) {
        preSum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return ret += preSum;
        }
        if (root.left != null) {
            dfs(root.left, preSum);
        }
        if (root.right != null) {
            dfs(root.right, preSum);
        }
        return ret;
    }

二叉树剪枝

思路：叶子节点为0 直接让它指向空后序遍历思想 1.遍历完左子树再遍历右子树 2. 如果遇到叶子节点则判断当前节点是否为0 3.如果为0 则直接返回null 否则不需要剪枝直接返回原来值

    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        } else {
            return root;
        }
    }

验证二叉搜索树

思路：二叉搜索树中序遍历是一个有序数组利用这一特性先定义一个最小数字prev 当遍历完左子树回退时候比较是否prev跟当前回退的数字大小如果比prev大则让prev=当前节点的值否则就不是二叉搜索树

    long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left) || root.val <= prev) {
            return false;
        }
        prev = root.val;
        return isValidBST(root.right);
    }

二叉搜索树中第 K 小的元素

思路：要求二叉搜索树第k大的数字定义俩个全局变量 ret记录最终结果 count记录当前k 依次遍历到左子树当为空的时候就该回退了并且 count-1 当count为0的时候就是目标值了

 int ret;
    int count ;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    public void dfs(TreeNode root) {
        if(root == null) {
            return ;
        }
        dfs(root.left);
        count--;
        if(count == 0) {
            ret = root.val;
            return ;
        }
        dfs(root.right);
    }

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

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

二叉树