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

    }