乐趣区

关于java:算法入门之深度优先

题目

leetcode938:二叉搜寻树的范畴和
给定二叉搜寻树的根结点 root,返回值位于范畴 [low, high] 之间的所有结点的值的和。

// 树结构
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {this.val = val;}

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
// 办法体
public class Solution {public int rangeSumBST(TreeNode root, int low, int high) {}}

思路

看到树这种无关的构造,首先想到就是深度优先或者广度优先,明天先用深度优先解这题。

深度优先模板

算法是有迹可循的,比方深度优先,实现根本用递归。

    // 万能递归模板
    private void recursion(TreeNode root) {if(root == null) {return;}
        // 解决逻辑在这里 前序遍历
        recursion(root.right);
        // 解决逻辑在这里 中序遍历
        recursion(root.left);
        // 解决逻辑在这里 后序遍历
    }

做题前先写下这个模板,这个就是深度优先遍历一颗树。具体题目,采纳其中摸一种遍历模式,而后做适当的形变即可。

做题

public int rangeSumBST(TreeNode root, int low, int high) {}

输出一个树,low,high,求树中处于 low,high 之间的和。
ok,咱们先写模板

public int rangeSumBST(TreeNode root, int low, int high) {if(root == null) {return 0;}
        rangeSumBST(root.right, low, high);

        rangeSumBST(root.left, low, high);
    }

root 是一个二叉搜寻树,排好序了的树,能够对 root.val 退出判断解决逻辑

public int rangeSumBST(TreeNode root, int low, int high) {if (root == null) {return 0;}
        if (root.val < low) {} else if (root.val > high) {} else {}
        rangeSumBST(root.right, low, high);

        rangeSumBST(root.left, low, high);
    }

如果根节点小于 low,右边就能够全副舍弃
如果根节点大于 high,左边就能够全副舍弃
如果根节点在 low,high 两头,那么就是左子树的值加上右子树的值加上根节点的值
最终变形为

public int rangeSumBST(TreeNode root, int low, int high) {if (root == null) {return 0;}
        if (root.val < low) {return rangeSumBST(root.right, low, high);
        } else if (root.val > high) {return rangeSumBST(root.left, low, high);
        } else {return rangeSumBST(root.right, low, high) + rangeSumBST(root.left, low, high) + root.val;
        }

    }
退出移动版