如何根据“前序遍历，中序遍历”，“中序遍历，后序遍历”构建按二叉树

绝地灬酷狼 2023-09-28 18:39 14阅读 0赞

> 如何根据前序遍历和中序遍历，或者中序遍历和后序遍历创建二叉树？大致思路如下文章；

[http://t.csdn.cn/wBUiy][http_t.csdn.cn_wBUiy]

--------------------

![c50be1c3e05c41d280fe88509667c07e.png][]

> 分析：

![7009b984e170470691921944a4ad842a.png][]

![872589f25eaa4d608704f8016f72b414.png][]

![65f13644e89641af85eb692d6521abcf.png][]

> 代码如下：

/**
     * 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 int preIndex;
        public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegan, int inEnd){
            //如果ib > ie说明递归终止
            if(inBegan > inEnd){
                return null;
            }
            //创建根节点
            TreeNode root = new TreeNode(preorder[preIndex]);
            //在中序遍历中找到对应的根节点下标
            int InorderIndex = fundInorderIndex(inorder, preorder[preIndex], inBegan, inEnd);
            //前序遍历中的下标继续往后遍历
            preIndex++;
            //通过递归继续创建左子树和右子树
            root.left = buildTreeChild(preorder, inorder, inBegan, InorderIndex - 1);
            root.right = buildTreeChild(preorder, inorder, InorderIndex + 1, inEnd);
            //最后返回根结点即可
            return root;
        }
        public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
            for(int i = inBegan; i <= inEnd; i++){
                if(inorder[i] == val){
                    return i;
                }
            }
            return -1;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
        }
    }

--------------------

![cdcd1edd4912469a963c38c65a0106de.png][]

> 分析：

和前序与中序遍历的思路一样，但是注意的是，后序遍历中是从后向前找根结点，因此，当你写出后序遍历的顺序的时候，会发现**需要先创建右子树，再创建左子树**。

> 代码如下：

/**
     * 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 int preIndex;
        public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegan, int inEnd){
            //如果ib > ie说明递归终止
            if(inBegan > inEnd){
                return null;
            }
            //创建根节点
            TreeNode root = new TreeNode(postorder[preIndex]);
            //在中序遍历中找到对应的根节点下标
            int InorderIndex = fundInorderIndex(inorder, postorder[preIndex], inBegan, inEnd);
            //前序遍历中的下标继续往后遍历
            preIndex--;
            //这里要注意，先构建左树再构建右树！
            root.right = buildTreeChild(postorder, inorder, InorderIndex + 1, inEnd);
            root.left = buildTreeChild(postorder, inorder, inBegan, InorderIndex - 1);
    
            //最后返回根结点即可
            return root;
        }
        public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
            for(int i = inBegan; i <= inEnd; i++){
                if(inorder[i] == val){
                    return i;
                }
            }
            return -1;
        }
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            preIndex = postorder.length - 1;
            return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
        }
    }

--------------------

![65c98cec03b94f1c90bd46bbbdd6fd5a.gif][]

[http_t.csdn.cn_wBUiy]: http://t.csdn.cn/wBUiy
[c50be1c3e05c41d280fe88509667c07e.png]: https://img-blog.csdnimg.cn/c50be1c3e05c41d280fe88509667c07e.png
[7009b984e170470691921944a4ad842a.png]: https://img-blog.csdnimg.cn/7009b984e170470691921944a4ad842a.png
[872589f25eaa4d608704f8016f72b414.png]: https://img-blog.csdnimg.cn/872589f25eaa4d608704f8016f72b414.png
[65f13644e89641af85eb692d6521abcf.png]: https://img-blog.csdnimg.cn/65f13644e89641af85eb692d6521abcf.png
[cdcd1edd4912469a963c38c65a0106de.png]: https://img-blog.csdnimg.cn/cdcd1edd4912469a963c38c65a0106de.png
[65c98cec03b94f1c90bd46bbbdd6fd5a.gif]: https://img-blog.csdnimg.cn/65c98cec03b94f1c90bd46bbbdd6fd5a.gif