使用 oh-my-zsh

105、 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

• 前序遍历 preorder = [3,9,20,15,7]
• 中序遍历 inorder = [9,3,15,20,7]
  返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

题解

1、二分递归构建

从前序遍历中找到根节点，在从中序遍历中找到左右子树区间

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildBTree(preorder,inorder,0,preorder.length - 1,0,inorder.length -1);
    }

    private TreeNode buildBTree(int[] preorder,int[] inorder,int pl,int pr,int il,int ir) {
        // 退出递归
        if (pl > pr || il > ir) {
            return null;
        }
        // 按照前序遍历 在中序遍历中 找到匹配的元素 将
        int rootVal = preorder[pl];
        int rootPos = 0;
        for (int i = il;i <= ir;i++) {
            if (inorder[i] == rootVal) {
                rootPos = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        // rootPos = 1
        // 递归构建左右子树
        root.left = buildBTree(preorder,inorder,pl+1,pl+rootPos-il,il,rootPos);
        root.right = buildBTree(preorder,inorder,pl+rootPos-il+1,pr,rootPos+1,ir);
        // 返回根节点
        return root;
    }
}

2、迭代法

借用栈存储前序遍历的元素，后序遍历用一个index维护。
思路类似于二叉树的迭代法中序遍历！！！

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 特殊情况
        if (preorder == null || preorfer,length == 0) {
            return null;
        }
        // 创建根节点
        TreenNode root = new TreeNode(preorder[0]);
        // 辅助栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        // 存放根节点
        stack.push(root);
        // 中序遍历指针
        int inorderIndex = 0;
        for (int i = 1;i < preorder.length;i++) {
            // 获取前序遍历的元素，根节点右边分别为 左子树 右子树
            int preorderVal = preorder[i];
            // 获取当前根节点
            TreeNode node = stack.peek();
            // 中序遍历的当前元素不是根节点，说明存在左子树
            if (node.val != inorder[inorderIndex]) {
                // 构建左子树
                node.left = new TreeNode(preorderVal);
                // 左子树入栈
                stack.push(node.left);
            } else {
                // 没有左子树了，构建右子树
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node.stack.pop();// 左子树根节点出栈
                    inorderIndex++;// 指针后移
                }
                // 构建右子树
                node.right = new TreeNode(preorderVal);
                // 右子树入栈
                stack.push(node.right);
            }
        }
        return root; // 返回根节点
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com