【每日一题】【dfs重载原始函数&循环/函数结束条件&左右下标在数组中位置的确定】2022年2月7日-NC12 由先序和中序遍历重建二叉树

描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

答案：

import java.util.*;

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {

        return reConstructBinaryTree(pre, 0 , pre.length - 1, vin, 0, vin.length - 1);

    }

    public TreeNode reConstructBinaryTree(int [] pre, int preStart, int preEnd, int [] vin, int vinStart, int vinEnd) {

        //注意：临界点是前后位置，pre和end永远不为空

        if(preStart > preEnd || vinStart > vinEnd) {

            return null;

        }

        TreeNode root = new TreeNode(pre[preStart]);

        for(int i = vinStart; i <= vinEnd; i++) {

            if(vin[i] == pre[preStart]) {

                //注意：先序的起始和结尾index，需要用vinStart和i表示

                root.left = reConstructBinaryTree(pre, preStart + 1, preStart + i - vinStart, vin, vinStart, i - 1);

                root.right = reConstructBinaryTree(pre, preStart + i - vinStart + 1, preEnd, vin, i + 1, vinEnd);

                //注意确定了node的左右子节点后，无需后续的遍历过程，直接break结束本次循环

                break;

            }

        }

        return root;

    }

}

注意：如果用i表示，那么（中序遍历中）左子树的下标位于先序遍历前面时，会导致i无法定位，所以不能用i表示，而应该用i和vin的元素个数关系表示

树的构造

public class TreeNode{

     int val;

     TreeNode left;

     TreeNode right;

     TreeNode(int val) {this.val = val;}

}

链表的构造：

public class LinkedNode{

     int val;

     LinkedNode next;

     LinkedNode(int val) { this.val = val; }

}

【每日一题】【dfs重载原始函数&循环/函数结束条件&左右下标在数组中位置的确定】2022年2月7日-NC12 由先序和中序遍历重建二叉树的相关教程结束。