889. 根据前序和后序遍历构造二叉树

分手后的思念是犯贱 2022-12-23 03:52 104阅读 0赞

# 题目来源 #

[889. 根据前序和后序遍历构造二叉树][889.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

我们知道，在前序遍历的时候，根节点是第一个输出，而在后序遍历中，根节点是最后一个输出；

那么我们可以利用前序遍历来构建Tree，然后通过后续遍历来检验当前树是否构建完毕。

首先我们创建一个节点作为 root，root = TreeNode(pre\[preIndex\])当 root.val == post\[posIndex\]时, 意味着我们已经构建完毕了当前子树，如果当前子树没有构建完毕，那么我们就递归的构建左右子树。

具体代码:

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
     int preIdx = 0, postIdx = 0;
        public TreeNode constructFromPrePost(int[] pre, int[] post) {
        
            TreeNode node = new TreeNode(pre[preIdx++]);
            if (node.val != post[postIdx]){
        
                node.left = constructFromPrePost(pre, post);
            }
            if (node.val != post[postIdx]){
        
                node.right = constructFromPrePost(pre, post);
            }
            
            postIdx++;
            return node;
        }
    }

[889.]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f8becbcb0fa749d89d1983677ce21fcf.png