236 二叉树最近公共祖先

code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // 对于每个节点，如果一个在左子树，一个在右子树，那答案就是他本身
    // 如果都在左子树，他一定不是，至少他的left是个答案，要往下挖到第一次的地方
    // [left, right]
    // [ true. true] [ true, false]
    // 一个节点，左边是一个，右边是另外一个，递归到这里就应该直接返回他
    // 一个节点，左边是一个，右边子树里有另外一个，返回他，跟上一行是同一个情况
    // 一个节点，左子树里一个，右子树里有另外一个，这个也是同一个情况，但我当前不可能知道
    // 自己是一个，自己的左/右子树里有另外一个，返回本人 
    // 返回情况应该只有这两种情况 
    // 所以递到最底层时候，我能判定的情况只有左右各一个的情况
    // 那返回值呢 
    // [left, right] 可以 [true, true]返回在左或者在右
    //   1
    //   2   3
    //  4 5  6 7 
    // 找4 7 呢，
    // 第一次不在 然后 同样递归 2 3
    // 2 这边反 [true, false] 那边返回 [false, true]
    // 1这边啥，自己的递归有任何一个是true，他就返回true上去
    function traverse(root){
        if(root === null){
            return null;
        }
        if(root === p || root === q){
            return root;
        }
        let left = traverse(root.left);
        let right = traverse(root.right);
        if(left !== null && right !== null){
            return root;
        }
        if(left !== null){
            return left;
        }
        if(right !== null){
            return right;
        }
        return null;
        
    }
    return traverse(root);
    
};

总结

1. 很反常.....大概能理解，不过我感觉至少得自己画一遍然后写两遍
2. 这期的表格没有简评更新了，反正是一个重点部分
3. 之后的评价和研究啥的之后再补吧