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

    }