美文网首页
LeetCode 106. 从中序与后序遍历序列构造二叉树

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

作者: 陈陈chen | 来源:发表于2021-09-01 16:39 被阅读0次

    1、题目

    image.png

    2、分析

    这道题的做法和第105题:从中序与前序遍历序列构造二叉树。一样的解法。
    只要找到中序遍历和后序遍历的规则,关键是找出迭代的索引位置就可以了。

    3、代码

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            return build(inorder, 0, inorder.length - 1, 
                         postorder, 0, postorder.length - 1);
        }
    
        private TreeNode build(int[] inorder, int inStart, int inEnd,
                               int[] postorder, int postStart, int postEnd){
            if (postStart > postEnd){
                return null;
            }
            int index = -1;
            int rootVal = postorder[postEnd];
            for (int i = inStart; i <= inEnd; i++){
                if (inorder[i] == rootVal){
                    index = i;
                    break;
                }
            }
            
            int rightSize = inEnd - index;
            TreeNode root = new TreeNode(rootVal);
            root.left = build(inorder, inStart, index - 1,
                              postorder, postStart, postEnd - rightSize - 1);
            root.right = build(inorder, index + 1, inEnd,
                               postorder, postEnd - rightSize, postEnd - 1);
            return root;
        }
    }
    

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/xnaxwltx.html