《剑指Offer》-04链表

重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(pre.length===0||vin.length===0){
        return null;
    }
    var index=vin.indexOf(pre[0]);
    
    var node=new TreeNode(pre[0]);
    node.left=reConstructBinaryTree(pre.slice(1,index+1),vin.slice(0,index+1));
    node.right=reConstructBinaryTree(pre.slice(index+1),vin.slice(index+1));
    return node;
}

小结：
递归思想
indexOf —-找到某元素的索引号
slice(x,y) —切片（范围包括x,不包括y）
前序遍历是中左右的顺序，中序遍历是左中右的顺序
那么对于{1,2,4,7,3,5,6,8}和{4,7,2,1,5,3,8,6}来说，1是根节点，然后1把中序遍历的序列分割为两部分，“4，7，2”为1的左子树上的节点，“5，3，8，6”为1的右子树上的节点，这样递归的分解下去即可

二叉树的下一个结点

题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(pNode)
{
    // write code here
    if(pNode==null){
        return null;
    }
    if(pNode.right!==null){//当前节点有右子树
        pNode=pNode.right;
        while(pNode.left!==null){
            pNode=pNode.left; //取最左节点
        }
        return pNode;
        
    }else{//当前节点无右子树
        while(pNode.next!==null){//不是根节点时
            if(pNode.next.left==pNode){ //当前节点是父元素的左子树
                return pNode.next;
            }else{//当前节点是父元素的右子树
                pNode=pNode.next;
            }
        }
        return null; //根节点返回null
    }
}

---

对称的二叉树

题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function isSymmetrical(pRoot)
{
    // write code here
    if(pRoot==null){
        return true;
    }
    var lr=function(p,q){
        if(p==null && q==null){
        return true;
    }
    if(p==null && q!==null){
        return false;
    }
    if(p!==null && q==null){
        return false;
    }
    if(p.val!==q.val){
        return false;
    }
    //递归，对称比较：左树左侧与右树右侧，左树右侧与右树左侧    
    return lr(p.left,q.right) && lr(p.right,q.left); 
    }
    return lr(pRoot.left,pRoot.right);
}

按之字形顺序打印二叉树

题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print(pRoot)
{
    // write code here
    const lists=[];
    if(pRoot===null){
        return lists;
    }
    const stack1=[];
    const stack2=[];
    stack1.push(pRoot);
    var i=1;
    while(stack1.length!==0||stack2.length!==0){
        const list=[];
        //奇数层
        if((i & 1)===1){
            while(stack1.length!==0){
                const tmp=stack1[stack1.length-1];
                list.push(tmp.val);
                stack1.pop();
                if(tmp.left!==null)stack2.push(tmp.left);
                if(tmp.right!==null)stack2.push(tmp.right);
            }
        }else{
         //偶数层
            while(stack2.length!==0){
                const tmp=stack2[stack2.length-1];
                list.push(tmp.val);
                stack2.pop();
                if(tmp.right!==null)stack1.push(tmp.right);
                if(tmp.left!==null)stack1.push(tmp.left);
            }
         }
        lists.push(list);
        i++;
    }
    return lists;
}

总结：
按之字形顺序打印二叉树，需要两个栈。当我们在打印某一行的结点时，把下一层的结点保存到相应的栈中。如果当前打印的是奇数层，则先保存左子结点再保存右子结点到一个栈中；如果当前打印的是偶数层，则先保存右子结点再保存左子结点到另一个栈中。
pop()——用于删除并返回数组的最后一个元素。
i & 1 ——与（AND）操作。只有 a 和 b 都是 1 时，a AND b 才是 1。

---

把二叉树打印成多行

题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print(pRoot)
{
    // write code here
    let lists=[];
    if(pRoot==null){
        return lists;
    }
    stack=[];
    stack.push(pRoot);
    while(stack.length!==0){
        let len=stack.length,
            temp=[],
            first;
        for(var i=0;i<len;i++){
            first=stack.shift();
            if(first.left){
                stack.push(first.left);
            };
            if(first.right){
                stack.push(first.right);
            }
            temp.push(first.val);
        }
        lists.push(temp);
    }
    return lists;
}

总结：
shift（）——把数组的第一个元素从其中删除，并返回第一个元素的值。
设置一个队列，操作n次（n为队列的长度），操作同时改变队列，去除队列首项，将操作后的项补到最后，一个循环结束后，原队列减一加一逐渐转换为下一层队列，循环操作

---

序列化二叉树

题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
var arr=[];
//使用递归先序遍历对二叉树进行序列化
function Serialize(pRoot)
{
    // write code here
    if(pRoot==null){
        arr.push("#");//空节点
    }else{
        arr.push(pRoot.val);
        Serialize(pRoot.left);
        Serialize(pRoot.right);
    }
    return arr;
}
//使用递归反序列化
function Deserialize(s)
{
    // write code here
    if(!arr || arr.length<=0){
        return null;
    }
    var rootVal=arr.shift();
    var root=null;
    if(typeof rootVal=="number"){ //判断节点是否为#
        root =new TreeNode(rootVal);
        root.left=Deserialize(arr);
        root.right=Deserialize(arr);
    }
    return root;
}

总结：
根据前序遍历规则完成序列化与反序列化。所谓序列化指的是遍历二叉树为字符串；所谓反序列化指的是依据字符串重新构造成二叉树。
依据前序遍历序列来序列化二叉树，因为前序遍历序列是从根结点开始的。当在遍历二叉树时碰到Null指针时，这些Null指针被序列化为一个特殊的字符“#”。

---

二叉搜索树的第k个结点

题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function KthNode(pRoot,k)
{
    // write code here
    if(pRoot===null || k===0){
        return null;
    }
    
// 为了能追踪k，应该把KthNodeCore函数定义在这里面，k应该在KthNodeCore函数外面（很重要）
    function KthNodeCore(pRoot){
        let target=null;
        if(pRoot.left){
            target=KthNodeCore(pRoot.left,k);//找到最小左子树的根节点
        }
        if(target==null){
            if(k===1){
                target=pRoot; //左子树为空，则根节点最小
            }
            k--;
        }
        if(target ===null && pRoot.right !==null){
            target=KthNodeCore(pRoot.right,k);  //从根节点起，往右子树查找第k小结点
        }
        return target;
    }
    return KthNodeCore(pRoot);
}

总结：

二叉树的分类、

满二叉树：从高到低，除了叶节点外，所以节点左右节点都存在。

完全二叉树：比满二叉树少几个叶节点，从左向右放子节点

平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。

二叉搜索树：空树或者二叉树的所有节点比他的左子节点大，比他的右子节点小。

红黑树：不仅是具有二叉搜索树的属性，还具有平衡树的属性，有序且子树差不超过1，颜色规则：根节点和特殊节点（即叶节点下面两个虚无的节点和未填写的节点）是黑的，红节点的左右子节点是黑的，最重要的是对于每个节点，从该节点到子孙叶节点的所有路径包含相同数目的黑节点。

---

数据流中的中位数

题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

let arr = []
function Insert(num) {
    // write code here
    if (arr.length === 0) {
        arr.push(num);
    } else{
        arr.push(num);
        let len=arr.length;
        //从大到小对数据进行排序
        if(num<arr[len-2]){
            for(var i=len-2;i>=0 && num<arr[i];i--){
                arr[i+1]=arr[i];//数组整体往后挪一个位置，方便num插入
            }
            arr[i+1]=num;
        }
    }
    return arr;
}
function GetMedian(){
	// write code here
    let len =arr.length;
    //奇数
    if((len%2)!==0){
        return(arr[(len-1)/2]);
    }
    //偶数
    else{
        return((arr[len/2]+arr[len/2-1])/2);
    }
}

总结：按题目的分区，应该用的大小堆做，不过好像挺麻烦，上面用的数组的排序
建立最大堆和最小堆，相当于排序，把中间的放在堆顶，左边放最大堆，右边放最小堆，这样就排序了
插入时间复杂度O(logn)，得到中位数时间复杂度O(1)