二叉树 binary tree

[xgqfrms]

二叉树 binary tree

前序遍历：根节点、左节点、右节点（1、2、4、5、7、8、3、6） 中序遍历：左节点、根节点、右节点（4、2、7、5、8、1、3、6） 后序遍历：左节点、右节点、根节点（4、7、8、5、2、6、3、1）

思路分析：根据前序中序可以推出整个二叉树，首先前序遍历的第一个数即位根节点，在中序中找到该数位置p，则该数左边的为左子树的中序元素，右边为右子树的中序元素，这时先序数组中第二个元素到p位置的元素也是左子树的先序元素，剩下p位置元素右边的就是treeeNode的右子树的先序子数组，找出这四组数值之后，分左右递归即可。

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

*/

function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(pre.length===0){return;}
    let treeNode = {
        val: pre[0]
    }
    for(let 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;
}

https://coffe1891.gitbook.io/frontend-hard-mode-interview/2/2.1.4

https://github.com/coffe1891/frontend-hard-mode-interview/issues/27

[xgqfrms]

/**
 * 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 {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {

};

https://leetcode.com/problems/binary-tree-paths/