二叉树实战

知识补充

（如果不是我这种对二叉树没什么概念的小菜鸡，直接到最底下去看看 [105]从前序与中序遍历序列构造二叉树的解题思路吧！）

在刷这道题之前，我们应该理解一下如何快速的从前序遍历、中序遍历、后序遍历【1】

• 前序遍历:
  • 前序遍历的遍历方式呢：根、左、右（根节点、和他的左右节点）
• 中序遍历:
  • 中序遍历的遍历方式呢：左、根、右
• 后序遍历:
  • 中序遍历的遍历方式呢：左、右、根

根据这个规则我们利用下面的这个例子简单的来做一个练习：

根据下面的二叉树，快速进行前序、后序、中序的序列遍历吧：

• 前序（根、左、右）：A B C D E F G H I
• 中序（左、根、右）：C B D A G F H E I
• 后序（左、右、根）：C D B G H F I E A

实战

光说不练假把式，说了这么多，没有用js实现都是纸上谈兵

二叉树的构造函数

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

前序遍历

二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 **遍历。

输入：root = [1,null,2,3] 输出：[1,2,3]

输入：root = [] 输出：[]

输入：root = [1] 输出：[1]

输入：root = [1,2] 输出：[1,2]

那么这道题的解题思路就很简单了

按照根-左-右的方式进行遍历就好

var preorderTraversal = function(root) {
    const res = []
    preorder(root, res)
    return res
};
const preorder = (root, res) => {
    if(root == null){
        return
    }
    res.push(root.val)
    preorder(root.left, res)
    preorder(root.right, res)
}

中序遍历

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

输入：root = [1,null,2,3] 输出：[1,3,2]

输入：root = [] 输出：[]

输入：root = [1] 输出：[1]

按照左、根、右的方式进行遍历就好

var inorderTraversal = function (root) {
  const res = []
  inorder(root, res)
  return res
};

const inorder = (root, res) => {
  if (root == null) {
    return
  }
  inorder(root.left, res)
  res.push(root.val)
  inorder(root.right, res)
}

仔细一看代码有没有一种？？？似曾相识的感觉？ 不错，我们就仅仅换了一个位置罢了！

后序遍历

145. 二叉树的后序遍历

一样我们记住公式和顺序，换汤不换药

按照 左、右、根

var postorderTraversal = function(root) {
  const res = []
  postorder(root, res)
  return res
};
// 按照左、右、根的顺序来就好
const postorder = (root,res) => {
  if(root === null){
    return
  }
  postorder(root.left, res)
  postorder(root.right, res)
  res.push(root.val)
}

到这里我们的前中后遍历大家就都应该简单懂了吧！

接下来。。。。。重头戏上场！

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入 : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

思路

我们需要紧紧抓住前序遍历序列和中序遍历序列的定义

• 前序遍历序列的第一个元素就是树的根节点
• 前序遍历的节点元素的后面的元素 先是左子树的所有节点而后是右子树的所有节点
  • 用示例 1举个例子**[3,9,20,15,7]**
    • 3 是二叉树的根节点
    • [9] 则是 二叉树的左子树的所有节点
    • [20,15,7]是右子树的所有节点
• 中序遍历中，根节点把中序遍历序列分成了两个部分，左边部分构成了二叉树的根节点的左子树，右边则是右子树
  • 举示例 1个例子**[9,3,15,20,7]**
    • 3 是二叉树的根节点
    • [9] 则是 二叉树的左子树的所有节点
    • [15,20,7]是右子树的所有节点

那我们的思路就有了：

• 我们可以根据当前前序遍历的第一个元素获取当前二叉树的根节点
• 利用二叉树的根节点 找到中序遍历的时候的位置，在中序遍历和前序遍历的时候，也就是节点的位置不同，但是左右节点的个数是相同的
• 这样我们就能确定他的左节点有多少，和右节点有多少个
• 这样我们就可以通过 parentIndex = inorder.indexOf(preorder[0]) 来获取切分左右节点的个数的位置
• 左节点：preorder.slice(1, parentIndex + 1)
• 右节点：preorder.slice(parentIndex + 1)

解法

var buildTree = function(preorder, inorder) {
  if(inorder.length === 0 || preorder.length === 0){
    return null
  }
  const res = new TreeNode(preorder[0])
  const parentIndex = inorder.indexOf(preorder[0])
  res.left = buildTree(preorder.slice(1, parentIndex + 1), inorder.slice(0, parentIndex))
  res.right = buildTree(preorder.slice(parentIndex + 1), inorder.slice(parentIndex + 1))
  return res
};

解析：

我们通过slice 每次就传入当前节点的左/右子节点元素的数组,所以我们可以确定，前序序列的数组的第一项肯定就是当前这个二叉树节点的根节点。

利用这个根节点我们通过查询中序序列的位置，我们可以得到这个根节点的左/右节点数组。

递归查询，即可

知识点归纳

【1】前序遍历 中序遍历 后序遍历

【2】105. 从前序与中序遍历序列构造二叉树 Construct Binary Tree from Preorder and Inorder Traversal

优秀博文推荐

东哥带你刷二叉树