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

飞熊 • 2023年4月6日下午12:51 • 技术随笔 • 阅读 190

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

http://t.csdn.cn/wBUiy

分析：

代码如下：

/**
 * 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);
    }
}

分析：

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

代码如下：

/**
 * 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);
    }
}