您的位置 首页 java

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

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

解法一:递归

根据中序遍历和后序遍历的性质,通过递归的方式求解,递归的过程如下:

  • 首先,如果中序遍历序列或后序遍历序列为空,直接返回空树;
  • 因为后序遍历序列的最后一个值为根节点,所以首先根据这个初始化得到当前的根节点 root
  • 然后根据根节点root在中序遍历序列中的位置,根节点前面的值都是当前根节点的左子树节点,得到当前根节点左右子树节点的数量;
  • 然后通过调用递归方法得到当前根节点的左右子树;
  • 最后返回root即为还原后的树。
 import com.kaesar.leetcode.TreeNode;

import java.util.Arrays;

public class LeetCode_106 {
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        // 如果中序遍历序列或后序遍历序列为空,直接返回空树
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        // 后序遍历序列的最后一个值为根结点的值
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);
        int leftCount = 0;
        // 中序遍历序列前面的值为左子树的节点,得到左子树的节点数量
        for (int val : inorder) {
            if (val != rootVal) {
                leftCount++;
            } else {
                break;
            }
        }
        // 递归得到当前根节点的左右子树
        root.left = buildTree(Arrays. copy OfRange(inorder, 0, leftCount), Arrays.copyOfRange(postorder, 0, leftCount));
        root.right = buildTree(Arrays.copyOfRange(inorder, leftCount + 1, inorder.length), Arrays.copyOfRange(postorder, leftCount, inorder.length - 1));
        return root;
    }

    public static  void  main(String[] args) {
        //  测试用例 
        // 中序遍历序列
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        // 后序遍历序列
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        buildTree(inorder, postorder).print();
    }
}  

【每日寄语】 命运负责洗牌,但是玩牌的是我们自己!

文章来源:智云一二三科技

文章标题:LeetCode-106-从中序与后序遍历序列构造二叉树

文章地址:https://www.zhihuclub.com/197823.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

2条评论

  1. That regiment is injectable ceftriaxone, in combination with one of two other oral antibiotics azithromycin or doxycycline Side Effects mood swings, blurred vision and the main side effect is weird dreams

网站地图