文章

每日LeetCode 181-182

2021.5.26 ・ 共 621 字,您可能需要 2 分钟阅读

Tags: LeetCode

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

 5
/ \

2 6 /
1 3

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder, 0, postorder.length - 1);
    }
    public boolean helper(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int index = left;
        while(postorder[index] < postorder[right]) {
            index++;
        }
        int temp = index;
        while (temp < right) {
            if (postorder[temp] < postorder[right]) {
                return false;
            }
            temp++;
        }
        return helper(postorder, left, index - 1) && helper(postorder, index, right - 1);
    }
}

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树,以及目标和 target = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[ [5,4,11,2], [5,8,4,5] ]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        backTracker(root, target);
        return ans;
    }

    public void backTracker(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            ans.add(new ArrayList(path));
        }
        backTracker(root.left, target);
        backTracker(root.right, target);
        path.remove(path.size() - 1);
    }
}

经典回溯