leetcode 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

题目

image.png

树的遍历

树的遍历：

  1. 前序遍历：先访问根节点，再访问左子树，然后访问右子树
  2. 中序遍历：先访问左子树，再访问根节点，然后访问右子树
  3. 后序遍历：先访问左子树，再访问右子树，然后访问根节点

根据遍历重建二叉树：前序遍历+后序遍历无法重建二叉树

  1. 前序+中序
  2. 中序+后序

前序 + 中序 重建二叉树的思路：

前序遍历结果：[3,9,20,15,7] 中序遍历结果：> [9,3,15,20,7]

  1. 由前序遍历的访问顺序可知，3 为 root 节点
  2. 由中序遍历的访问顺序可知，[9] 为 root 节点的左子树遍历结果，[15,20,7] 为 root 节点的右子树遍历结果

解法

  1. 遍历解法：思路为根据前序遍历的顺序重构二叉树，然后使用中序遍历作为条件来调整节点的位置

    1. 使用 preindex 来记录前序遍历数组访问到的位置，inindex 来记录中序遍历数组所访问到的位置
    2. 使用一个遍历函数来进行重建二叉树： ```java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }

    • } */ class Solution { // 通过遍历来重构树 int preindex = 0; int inindex = 0;

      public TreeNode buildTree(int[] preorder, int[] inorder) { return dfs(preorder, inorder, null); }

      private TreeNode dfs(int[] preorder,int[] inorder,TreeNode finish){ // 退出循环的两个可能情况： // 1.前序遍历完成 // 2.左子树遍历完成 if (preindex == preorder.length || (finish != null && inorder[inindex] == finish.val)){

      1.    return null;

      }

      // 前序遍历：先是根节点，然后为左右节点 TreeNode root = new TreeNode(preorder[preindex++]); // 左子树 root.left = dfs(preorder, inorder, root);

      inindex++; // 右子树 root.right = dfs(preorder, inorder, finish); return root; } } ```