二叉树的构造

[TieMuZhen]

将数组转化为二叉树

数组和二叉树的关系

二叉树可以通过数组来进行存储。
​数组从0开始，如果父节点在数组中的下标是i，那么其左孩子在数组中对应的下标则为2i+1。右孩子对应的下标为2i+2。
同理，已知某节点在数组中对应的下标为i，那么其父亲节点对应的下标为i/2;

代码实现

// arr = [1, 2, 3, 4, 5, 6];
// 将数组转为层次遍历的二叉树，效果如下
//                  1
//               /     \
//             2        3
//           /   \     /  
//          4    5   6 


/**
 * @param {number[]} arr
 * @return {TreeNode} root
 */
function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}

function createTree(arr, index){
    if(index > arr.length - 1) return null;
    let root = new TreeNode(arr[index]);
    root.left = createTree(arr, 2 * index + 1);
    root.right = createTree(arr, 2 * index + 2);
    return root;
}

var buildTree = function(arr){
    return createTree(arr, 0);
}

前序遍历构造二叉树并返回高度

function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}

let path = 'NNLLL', cur = 0;

// 前序遍历构造二叉树
function buildTree(){
    if(path[cur++] == 'L'){
        return new TreeNode('L');
    }
    let root = new TreeNode('N');
    root.left = buildTree();
    root.right = buildTree();
    return root;
}

// 前序输出验证与给定的字符串是不是一样
let heigh = 0;
function preOrder(root){
    if(root == null) return; // 一定要判空，千万不要忘了！！！！
    console.log(root.val)
    preOrder(root.left);
    preOrder(root.right);
}

// 获取二叉树高度
function getHeigh(root){
    if(root == null){
        return 0;
    }
    let left = getHeigh(root.left);
    let right = getHeigh(root.right);
    return Math.max(left + 1, right + 1); // 重点
}

function run(){
    let root = buildTree();
    preOrder(root);
    console.log(getHeigh(root));
}

从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
// 查询前序遍历中的元素在中序遍历中的位置
function findIndex(data, inorder){
    let index = 0;
    for(let i = 0; i < inorder.length; i++){
        if(data == inorder[i]){
            index = i;
        }
    }
    return index;
}
var buildTree = function(preorder, inorder) {
    // 边界条件 && 递归出口
    if(!preorder.length) return null;

    let data = preorder[0];
    let index = findIndex(data, inorder);
    let root = new TreeNode(data); // 构建二叉树的根节点
    // 构建二叉树的左子树reConstructBinaryTree(左子树的前序数组, 左子树的中序数组)
    root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
    // 构建二叉树的右子树reConstructBinaryTree(右子树的前序数组, 右子树的中序数组)
    root.right = buildTree(preorder.slice(index + 1, preorder.length), inorder.slice(index + 1, inorder.length));
    return root;
};