Day 15

剑指offer 33.二叉搜索树的后序遍历序列

题目描述

解答

lass Solution {
     public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int left, int right) {
        //（结束条件最后看！）左右指针重合的时候，即left~right区间只有一个数
        if (left >= right) {
            return true;
        }
        //在后序遍历中根节点一定是最后一个点
        int root = postorder[right];
        int index = left;
        while (postorder[index] < root) {
            index++;
        }
        int m = index;//left~right之间第一个比root大的点，即root右子树中最小的点（右子树后序遍历的起点）
        //如果m~right区间（root的右子树）出现了比root小的节点，则不可能是后序遍历
        while (index < right) {
            if (postorder[index] < root) {
                return false;
            }
            index++;
        }
        //此时能保证left ~ m-1都比root小，m ~ right-1都比root大，但这两个子区间内部的情况需要继续递归判断
       & return recur(postorder, left, m - 1) & recur(postorder, m, right - 1);
    }
}

剑指offer 34.二叉树中和为某一值的路径

题目描述

思路–回溯算法

由于必须要从根节点开始，因此要用前序遍历（DFS）

回溯算法的核心就是：一条路没走通，路径返回一步，再走

解答

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    // 构造recur(root，tar)函数，作用是将符合条件的path，加入到res中
    void recur(TreeNode root, int tar) {
        // 递归结束条件
        if(root == null) return;
        // 将当前根节点加入到路径中
        path.add(root.val);
        tar -= root.val;
        //如果是叶子节点，并且和刚好为sum，将组合加入res
        if(tar == 0 && root.left == null && root.right == null){
            //将 path 拷贝到新的newPath中
            LinkedList newPath=new LinkedList<>(path);
        	//将 newPath 加入到结果集 res 中
            res.add(newPath);
        }
       // 如果不是叶子节点，继续递归，直到递归结束
        if(root.left!=null)
        recur(root.left, tar);
        if(root.right!=null)
        recur(root.right, tar);
       // 如果一条路遍历到底，root=null 还不满足tar==0，路径回退一步， 即删除路径中的最后一个节点值
        path.removeLast();
    }
}