二叉树常见面试题

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

function reConstructBinaryTree(pre, vin) {
    if (!pre || pre.length === 0) {
        return;
    }
    var treeNode = {
        val: pre[0]
    }
    for (var i = 0; i < pre.length; i++) {
        if (vin[i] === pre[0]) {
            treeNode.left = reConstructBinaryTree(pre.slice(1, i + 1), vin.slice(0, i));
            treeNode.right = reConstructBinaryTree(pre.slice(i + 1), vin.slice(i + 1));
        }
    }
    return treeNode;

}

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

function HasSubtree(pRoot1, pRoot2) {
    if (!pRoot1 || !pRoot2) {
        return false;
    }
    return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}

function isSubtree(root1, root2) {
    if (!root2) {
        return true;
    }
    if (!root1) {
        return false;
    }
    if (root1.val == root2.val) {
        return isSubtree(root1.left, root2.left) &&
            isSubtree(root1.right, root2.right);
    } else {
        return false;
    }
}

二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

function Mirror(root) {
    if (root === null) {
        return;
    }
    var temp = root.left;
    root.left = root.right;
    root.right = temp;
    Mirror(root.left);
    Mirror(root.right);
}

从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

function PrintFromTopToBottom(root) {
    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;
}

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同

function VerifySquenceOfBST(sequence) {
    if (!sequence.length) {
        return false;
    }
    return adjustSquence(sequence, 0, sequence.length - 1);

}

function adjustSquence(sequence, start, end) {
    if (start >= end) {
        return true;
    }
    var i = start;
    while (i < end && sequence[i] < sequence[end]) {
        i++;
    }
    for (var j = i; j < end; j++) {
        if (sequence[j] < sequence[end]) {
            return false;
        }
    }
    return adjustSquence(sequence, start, i - 1) && adjustSquence(sequence, i, end - 1)
}

二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

function FindPath(root, expectNumber) {
    var result = [];
    if (root === null) {
        return result;
    }
    dfsFind(root, expectNumber, [], 0, result);
    return result;

}

function dfsFind(root, expectNumber, path, currentSum, result) {
    currentSum += root.val;
    path.push(root.val);
    if (currentSum == expectNumber && root.left == null && root.right == null) {
        result.push(path.slice(0));
    }
    if (root.left != null) {
        dfsFind(root.left, expectNumber, path, currentSum, result);
    }
    if (root.right != null) {
        dfsFind(root.right, expectNumber, path, currentSum, result);
    }
    path.pop();
}

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

function TreeDepth(pRoot) {
    if (!pRoot) return 0;
    var left = 1 + TreeDepth(pRoot.left);
    var right = 1 + TreeDepth(pRoot.right);
    return Math.max(left, right)
}

平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
var isBalanced = true;
function IsBalanced_Solution(pRoot) {
    if (pRoot == null) {
        return true;
    }
    IsBalanced(pRoot);
    var result = isBalanced;
    isBalanced = true;
    return result;
}
function IsBalanced(pRoot) {
    if (pRoot == null) {
        return 0;
    }
    var left = 0,
        right = 0;
    if (pRoot.left) {
        left = IsBalanced(pRoot.left);
    }
    if (pRoot.right) {
        right = IsBalanced(pRoot.right);
    }
    if (Math.abs(left - right) > 1) {
        isBalanced = false;
    }
    return left > right ? left + 1 : right + 1;
}

二叉树的下一个结点

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

function GetNext(pNode) {
    if (pNode == null) {
        return null;
    }
    var iNext = null;
    if (pNode.right != null) {
        var iRight = pNode.right;
        while (iRight.left != null) {
            iRight = iRight.left;
        }
        iNext = iRight;
    } else if (pNode.next != null) {
        var iCurrent = pNode,
            iParent = pNode.next;
        // 纪录一对结点，判断pNode是其父结点的左孩子还是右孩子
        while (iParent != null && iCurrent == iParent.right) {
            iCurrent = iParent; //沿父指针向上查找
            iParent = iCurrent.next;
        }
        // 直到找到某一结点是其父结点的左孩子，iNext就是该节点的父
        iNext = iParent;
    }
    return iNext;
}

对称的二叉树

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

function isSymmetrical2(root1, root2) {
    if (root1 == null && root2 == null) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    if (root1.val != root2.val) {
        return false;
    }
    return isSymmetrical2(root1.left, root2.right) && isSymmetrical2(root1.right, root2.left);
}

function isSymmetrical(pRoot) {
    return isSymmetrical2(pRoot, pRoot)
}

按之字形顺序打印二叉树

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

function Print(pRoot) {
    if (!pRoot) {
        return [];
    }
    var queue = [],
        result = [],
        flag = true;
    queue.push(pRoot);
    while (queue.length) {
        var len = queue.length;
        var tempArr = [];
        for (var i = 0; i < len; i++) {
            var temp = queue.shift();
            tempArr.push(temp.val);
            if (temp.left) {
                queue.push(temp.left);
            }
            if (temp.right) {
                queue.push(temp.right);
            }
        }
        if (!flag) {
            tempArr.reverse();
        }
        flag = !flag;
        result.push(tempArr);
    }
    return result;
}

把二叉树打印成多行

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

function Print(pRoot) {
    if (!pRoot) {
        return [];
    }
    var queue = [],
        result = [];
    queue.push(pRoot);
    while (queue.length) {
        var len = queue.length;
        var tempArr = [];
        for (var i = 0; i < len; i++) {
            var temp = queue.shift();
            tempArr.push(temp.val);
            if (temp.left) {
                queue.push(temp.left);
            }
            if (temp.right) {
                queue.push(temp.right);
            }
        }
        result.push(tempArr);
    }
    return result;
}

序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

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('a');
    } else {
        arr.push(pRoot.val);
        Serialize(pRoot.left);
        Serialize(pRoot.right);
    }

}
function Deserialize(s) {
    // write code here
    var node = null;
    if (arr.length < 1) {
        return null;
    }
    var number = arr.shift();
    if (typeof number == 'number') {
        node = new TreeNode(number);
        node.left = Deserialize(arr);
        node.right = Deserialize(arr);
    }
    return node;
}

二叉搜索树的第k个结点

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

function Index() {
    this.index = 0;
}
function KthNode(pRoot, k) {
    if (pRoot === null) {
        return null;
    }
    let index = new Index();
    return Inorder(pRoot, k, index)
}
function Inorder(pRoot, k, index) {
    if (pRoot === null) {
        return null;
    }
    let node = Inorder(pRoot.left, k, index);
    if (node) return node;
    if (++index.index === k) {
        return pRoot;
    }
    node = Inorder(pRoot.right, k, index);
    if (node) return node;
}