114 二叉树展开为列表

函数签名如下：

void flagtten (TreeNode root)

尝试给出这个函数的定义：

给flatten 函数输入一个节点root，那么以root为根的二叉树就会被拉平为一条链表。

（具体操作）

这就是递归的魅力，你说?flatten?函数是怎么把左右子树拉平的？说不清楚，但是只要知道?flatten?的定义如此，相信这个定义，让?root?做它该做的事情，然后?flatten?函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。

public void flatten(TreeNode root) {
		//base case
    if(root == null) return ;
    flatten(root.left) ;
    flatten(root.right);
    //后序遍历，要先拉平左右子树才能进行后序操作
    // 1、 左右子树已经被拉平成一条链表。
    TreeNode left = root.left ;
    TreeNode right = root.right ;

    //2、将左子树作为右子树
    root.left = null;
    root.right = left ;

    //3 将原先的右子树接到当前右子树的末端
    TreeNode  p = root;
    while(p.right != null) {
    	p = p.right ;
    }
    p.right = right ;
  }

总结

递归算法的关键要明确函数的定义，相信这个定义，我们先要搞清楚root节点它自己要做什么。

二叉树题目的难点在于如何通过题目的要求思考出每一个节点需要做什么。

回溯算法

模板

思考三个问题：

路径：也就是已经做出的选择
选择列表：也就是你当前可以做的选择
结束条件：也就是到达决策树底层，无法再做选择的条件。

// 框架
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：

void traverse(TreeNode root) {
    for (TreeNode child : root.childern)
        // 前序遍历需要的操作
        traverse(child);
        // 后序遍历需要的操作
}

而所谓的前序遍历和后序遍历，他们只是两个很有用的时间点。

集合划分问题

698 划分为k个相等的子集

两个视角，分别从数字和痛的角度来看。

以数字的视角

//主函数
public boolean canPartitionKSubsets(int[] nums, int k) {
	//排除一些基本情况
    if(k > nums.length) return false ;
    int sum = 0 ;
    for(int v : nums) sum += v;
    if(sum % k != 0) return false ;

    //k个桶（集合），记录每个桶装的数字之和
    int[] bucket = new int[k] ;
    // 理论上每个桶 中数字的和
    int target = sum/k;
    //通过排序让大的数在前，从而更容易命中 回溯过程中的if语句，达到减少时间复杂度的效果。
    // JAVA语言的特性，先排列，再置换。
    /* 降序排序 nums 数组 */
    Arrays.sort(nums);
    for (i = 0, j = nums.length - 1; i < j; i++, j--) {
        // 交换 nums[i] 和 nums[j]
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    /*******************/
    //穷举
    return  backtrack(nums, 0, bucket, target);
}

public boolean backtrack(int[] nums,int index ,int[] bucket,int target){
    if(index == nums.length) {
    	// 检查所有桶的数字之和是否都是target
        for(int i=0;i<bucket.length;i++) {
        	if(bucket[i]!=target) {
            	return false ;
            }
        }
        // nums 成功平分成k个子集
        return true;
    }

    //穷举 nums[index] 可能装入的桶
    for(int i=0;i<bucket.length;i++) {
    	// 剪枝，桶装满了
        if(bucket[i] + nums[index] > target) {
        	continue ;
        }
        //将nums[index] 装入bucket[i]
        bucket[i] += nums[index] ;
        //递归穷举下一个数字的选择
        if(backtrack(nums,index+1,bucket,target)) return true ;
        //撤销选择
        bucket[i] -= nums[index] ;
    }

    //nums[index] 装入哪个桶都不行
    return false ;
}