ORID25

睡眠质量真的影响自己第二天的心情……我觉得做完就睡的很好，然后早上起来神清气爽，做事情也很高兴。就是不会觉得自己脑子混混僵僵的，所以保证自己有一个好的睡眠质量真的很重要，能让自己第二天有个好心情做事。

[235&236] Lowest common ancestor of a binary search tree解题报告

算法

用divide and conquer 算法
为什么用这个算法（那些条件）？
因为这是一个二叉树，所以可以用divide and conquer来实现
为了找到他们的“祖先”，或者说上一级，你就需要能够不断的从这个节点往下面走，直到走到p或者q的位置，然后返回他们的祖先。

代码实现

有什么要注意的地方
判断条件要想清楚，因为你在递归的时候要判断返回什么？以及什么条件才能返回它？

if (root == null || root == p || root == q) {
    return root;
}

这里为什么要return root呢？因为一旦root等于null，那么就是你递归到二叉树的最底部了，并且在过程中你没有找到p 或者 q， 所以返回root，如果找到了，那么返回root（如果直接看这一行可能会有点蒙，但看到后面你就知道为什么要返回root了），因为你在递归进入到下一层的时候，你pass的参数是：
root.left(or root.right), p , q
所以实际上这时候如果你找到了p，q的祖先，返回的将是当前root
以下是整段代码

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        //这上面是返回条件（递归的出口），也就是递归时候的返回条件
        //这下面是divide部分，分成左和右
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //conquer部分，一开始看起来有点蒙，但是你看一下出口的条件就明白了，left != null 就意味着左边找到了其中一个祖先， right != null也一样，      
        //只有当他俩同时不是null的时候才说明找到了共同祖先。否则只是找到了其中一个（其实如果这个二叉树必须有个root，以及给你的两个node都 
        //存在在这棵树上面，那后面的判断已经没必要了。因为这一行就确保你找到p和q，最差最差也会return root（也就是根部）

        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;

    }

有什么可以优化的地方
无

时空复杂度分析

O(n) 因为最坏情况你就要把每一个node都走一遍。

相关题目有哪些做过的

跟哪个题目比较像？
目前没想到……

[124] Binary tree maximum path sum解题报告

算法

用什么算法
Divide and conquer
为什么用这个算法（那些条件）？
因为要用递归来寻找到最大的路径

代码实现

有什么要注意的地方
这题要注意的地方实在是太多了……我一开始的方法没错（D&C），结果好多edge case弄得我焦头烂额，不断加if else的判断，但是最后始终有问题，比如只给你[-3], or [-2, -1],or [1, -2, 3] 我一开始只是把左右拆开，return最大值（由于出口设置的值为0，所以最后到null之后一定返回0，但是如果整棵树上都是负数，那返回的值就不对了。）
然后我就改了一下，可以返回负数，但是发现负数也有个问题，就是如果root为负数，你要考虑他的孩子是否比他大，如果root不为负数，你要考虑左右两边是否曾经有过负数。比如这个例子[1,-2,-3,1,3,-2,null,-1]
返回的值就应该是3，因为3是在-2下面的，如果你最后返回4就错了……我当时还在想是否要用boolean flag去验证路径上是否有负数，结果还是有问题。

最后看了别人的答案，发现最好的方式还是要用一个global variable，然后keep track of max value. 而且必须用root.val + left + right compare to max 这样你就直接知道了当前节点和他的孩子的和是否比max大，如果大就保存起来，如果不是就不保存。
这是那个人的代码

public class Solution {
    int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    // helper returns the max branch 
    // plus current node's value
    int helper(TreeNode root) {
        if (root == null) return 0;
        
        int left = Math.max(helper(root.left), 0);
        int right = Math.max(helper(root.right), 0);
        
        max = Math.max(max, root.val + left + right); //这个就是在记录最大值, 而且不会受到全是负数的影响，因为如果底下两层是负数，他在上两句的      
                                                     //时候已经把他们变为0了，而之前也记录了他们的最大值（上一次递归的时候会记录负数的最大值，
                                                    //因为MIN_VALUE 比任何负数都要小，这时候相加只得到root.val并且把它和之前的最大值比较。
        
        return root.val + Math.max(left, right);  //这其实保证了负数会被返回上一层
    }
}

有什么可以优化的地方

时空复杂度分析

...

相关题目有哪些做过的

跟哪个题目比较像？
都是divide and conquer