手把手带你刷二叉树（第一期）

「该做什么」就是让你想清楚写什么代码能够实现题目想要的效果，所谓「什么时候做」，就是让你思考这段代码到底应该写在前序、中序还是后序遍历的代码位置上。

我们直接上几道比较有意思，且能体现出递归算法精妙的二叉树题目

二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

这道题目比较简单，关键思路在于我们发现翻转整棵树就是交换每个节点的左右子节点，于是我们把交换左右子节点的代码放在了前序遍历的位置。


如果把交换左右子节点的代码复制粘贴到后序遍历的位置也是可以的，但是直接放到中序遍历的位置是不行的。

var invertTree = function(root) {
    if (root==null) return null;
    let left = invertTree(root.left)
    let right = invertTree(root.right)
    root.left = right
    root.right = left
    return root
};

116. 填充每个节点的下一个右侧节点指针 （中等）

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

第一感觉就是层次遍历，可以得到每一行的节点，for循环连接就行了。

文章使用递归：

问题在于每个节点的左右子节点都穿起来是不够的

function connectTwoNode(node1, node2) {
    if(node1 == null) return;
    // 前序遍历
    node1.next = node2
    // 能否覆盖整棵二叉树,模拟3层即可
    connectTwoNode(node1.left, node1.right)
    connectTwoNode(node1.right, node2.left)
    connectTwoNode(node2.left, node2.right)

}
var connect = function(root) {
    if(root == null) return null;
    connectTwoNode(root.left, root.right)
    return root
};

114. 二叉树展开为链表（中等）

没头绪，直到看到此图：

函数有返回值，容易理解。但不返回函数的定义也一样，

给 flatten 函数输入一个节点 root，那么以 root 为根的二叉树就会被拉平为一条链表。

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    if(root == null) return null
    let left = flatten(root.left)
    let right = flatten(root.right)

    root.left = null
    root.right = left
    let last = root
    while(last.right) last = last.right
    last.right = right

    return root; 
};

flatten完后，root的左右子树已经是扁平化了。直接拿来用就可以。

if (root == null) return;
flatten(root.left);
flatten(root.right);

/**** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;

手把手带你刷二叉树（第二期）

把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了

654. 最大二叉树 （中等）

该约束保证创建的二叉树是唯一的

重新写一个辅助函数 build，来控制 nums 的索引

function getIndex(nums, left, right){
    let index = left, temp = nums[left]
    for(let i=left+1; i<=right; i++) {
        if(temp<nums[i]) {
            index = i
            temp = nums[i]
        }
    }
    return index
}
function build(nums, start, end) {
    if(start>end) return null
    let index = getIndex(nums, start, end)
    let root = new TreeNode(nums[index])
    root.left = build(nums, start, index-1)
    root.right = build(nums, index+1, end)
    return root
}
var constructMaximumBinaryTree = function(nums) {
    return build(nums, 0, nums.length-1)
};

105. 从前序与中序遍历序列构造二叉树 （中等）

经典笔试题，现在要代码实现。前序数组的第一个元素用来分割中序数组。发现如果不记住两个数组的开始结束索引，就得每次传新的缩小的数组。

var buildTree = function(preorder, inorder) {    
    function build(pre, ino) {
        if(pre.length == 0) return null
        let root = new TreeNode(pre[0])
        let index = ino.indexOf(pre[0])
        // index说明前面有多少个节点在左子树
        let lpre = pre.slice(1,index+1) // 左闭右开
        let lino = ino.slice(0, index)
        let rpre = pre.slice(index+1)
        let rino = ino.slice(index+1)
   
        root.left = build(lpre, lino)
        root.right = build(rpre, rino)
        return root;
    }
    return build(preorder, inorder)
};

使用索引来规范在数组

对于左右子树对应的 inorder 数组的起始索引和终止索引比较容易确定：



对于 preorder 数组呢？如何确定左右数组对应的起始索引和终止索引？

var build = function(pre, preS, preE, ino, inoS, inoE) {
    if(preS > preE) return null;
    // root 节点对应的值就是前序遍历数组的第一个元素
    let rootVal = pre[preS];
    // rootVal 在中序遍历数组中的索引
    let index = ino.indexOf(rootVal)
    let leftSize = index - inoS;

    // 先构造出当前根节点
    let root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(pre, preS + 1, preS + leftSize,
                      ino, inoS, index - 1);

    root.right = build(pre, preS + leftSize + 1, preE,
                       ino, index + 1, inoE);
    return root;
}

var buildTree = function(preorder, inorder) {    
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
};

106. 从中序与后序遍历序列构造二叉树

做完前面一题，这题就不难了，看懂下图，索引自然会写

function build(post, postS, postE, ino, inoS, inoE) {
    if(postS > postE) return null
    let val = post[postE]
    let index = ino.indexOf(val)
    // 因为index是针对ino的,所以可以直接使用,而在post就不适用了
    let leftsize = index - inoS
    let root = new TreeNode(val)
    root.left = build(post, postS, postS+leftsize-1,
                    ino, inoS, index-1,)
    root.right = build(post, postS+leftsize, postE-1,
                    ino, index+1, inoE)
    return root;
}
var buildTree = function(inorder, postorder) {
    return build(postorder, 0, postorder.length-1, inorder, 0, inorder.length-1)
};

889. 根据前序和后序遍历构造二叉树 (fail)

为什么呢？我们说过，构建二叉树的套路很简单，先找到根节点，然后找到并递归构造左右子树即可。

前两道题，可以通过前序或者后序遍历结果找到根节点，然后根据中序遍历结果确定左右子树。

这道题，你可以确定根节点，但是无法确切的知道左右子树有哪些节点。

所以问题出发点：找到能分割后序遍历左右子树的点。因为后序遍历是 左右根，在遍历根节点的右子树之前，最后一个遍历的是左子树的根节点。所以：

使用到前序遍历的第一、第二个值，要保证开始结束索引大于1

代码：

function build(preorder, preStart, preEnd,
                postorder, postStart, postEnd) {
    if (preStart > preEnd) return null;
    if (preStart == preEnd) return new TreeNode(preorder[preStart]);
    // root 节点对应的值就是前序遍历数组的第一个元素
    let rootVal = preorder[preStart];
    // root.left 的值是前序遍历第二个元素
    // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
    // 确定 preorder 和 postorder 中左右子树的元素区间
    let leftRootVal = preorder[preStart + 1];
    // leftRootVal 在后序遍历数组中的索引
    let index = postorder.indexOf(leftRootVal)
    // 后序数组中左子树的元素个数
    let leftSize = index - postStart + 1;

    // 先构造出当前根节点
    let root = new TreeNode(rootVal);
    // 递归构造左右子树
    // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
    root.left = build(preorder, preStart + 1, preStart + leftSize,
            postorder, postStart, index);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
            postorder, index + 1, postEnd - 1);

    return root;
}

var constructFromPrePost = function(preorder, postorder) {
    return build(preorder, 0, preorder.length - 1,
                postorder, 0, postorder.length - 1);
};