剑指offer刷题记录（树篇）

1.重建二叉树

注意：pre.length为 1的时候，root不是全局变量，所以写的不是root，而是pre[0] 调试了半天才出来的结果。还有vin.length和pre.length尽量加上。

function reConstructBinaryTree(pre, vin)
{

    // write code here
    var result = null;
   
        if(pre.length>1){
             var root = pre[0]
        var rootIndex = vin.indexOf(root);
        var leftVin = vin.slice(0,rootIndex);
        var rightVin = vin.slice(rootIndex+1,vin.length);
        pre.shift();
        var leftPre = pre.slice(0,leftVin.length);
        var rightPre = pre.slice(leftVin.length,pre.length);
            result = {
                val:root,
                left:reConstructBinaryTree(leftPre,leftVin),
                right:reConstructBinaryTree(rightPre,rightVin)
            }
        }else if(pre.length==1){
            result = {
                val:pre[0],
                left:null,
                right:null
            }
        }
    return result;
}

2.二叉树的镜像

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Mirror(root)
{
    if(root==null) {return null;}
    if(root.left==null&&root.right==null){
        return null;
    }
        var temp = root.left;
        root.left = root.right;
        root.right = temp;
        if(root.left){
            Mirror(root.left)
        }
        if(root.right){
            Mirror(root.right);
        }
}

3.从上往下打印二叉树

需要借助一个栈来实现效果

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function PrintFromTopToBottom(root)
{
    // write code here
    var arr = [];
    var data = [];
    if(root!==null){
        arr.push(root)
    }
    while(arr.length!=0){
        var node = arr.shift();
        if(node.left!=null){
            arr.push(node.left)
        }
        if(node.right!=null){
            arr.push(node.right)
        }
        data.push(node.val);
    }
    return data;
}