欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-05 21:13:27
leetcode-105 从前序与中序遍历序列构造二叉树前序的第一个节点是根节点,然后在中序中找到这个节点的位置,该位置前为左子树,后为右子树。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class...

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

前序的第一个节点是根节点,然后在中序中找到这个节点的位置,该位置前为左子树,后为右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight){
        if (preLeft > preRight) return null;
        int i = 0;
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 查找根节点在中序中的位置
        for (i = inLeft; i <= inRight; i++){
            if (inorder[i] == preorder[preLeft]){
                break;
            }
        }
        // 构建左子树
        root.left = buildTree(preorder, preLeft + 1, preLeft + (i - inLeft), inorder, inLeft, i - 1);
        // 构建右子树
        root.right = buildTree(preorder, preLeft + 1 + (i - inLeft), preRight, inorder, i + 1, inRight);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return root;
    }
}

本文地址:https://blog.csdn.net/liu_tian_wei/article/details/109637936