LeeCode-刷题日记-Day31

236. 二叉树的最近公共祖先

思路：遍历到底，自底向上进行标记。如果此节点左、右子树都满足有要求的节点，那么它就是我们要找的公共节点。

所以当满足，lson与rson同时为1时得到公共祖先。

同时，如果当前节点等于其中一个值，且子树满足条件。那么它也是公共祖先。

返回值为当前子树是否含有指定节点。

/**
 * 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) {
    let ans;
    function dfs(root,p,q){
        if(root===null) return false;
        let lson=dfs(root.left,p,q);
        let rson=dfs(root.right,p,q);
        if((lson&&rson)||((root.val===p.val||root.val===q.val)&&(rson||lson))){
            ans=root;
        }
        return lson||rson||root.val===q.val||root.val==p.val;
    }
    dfs(root,p,q);
    return ans;
};

297. 二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    return rserialize(root,'')
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    let datalist = data.split(",");
    return rdeserialize(datalist)
};

function rserialize(root,str){
    if(root===null){
        str+="None,";
    }else{
        str +=root.val+''+',';
        str=rserialize(root.left,str);
        str=rserialize(root.right,str);
    }
    return str;
}

function rdeserialize(data){
    if(data[0]==='None'){
        data.shift();
        return null;
    }
    const root=new TreeNode(parseInt(data[0]));
    data.shift();
    root.left=rdeserialize(data);
    root.right=rdeserialize(data);
    return root;
}
/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */