二叉树中已知先序和中序，请画出这颗二叉树

二叉树中已知先序和中序，请画出这颗二叉树
了解什么是前序遍历，中序遍历，后序遍历

img

先看先序序列，A是第一个，所以A为根节点；
继续先序序列，下一个是B，但不知道B在A左边还是右边，所以要看中序序列，发现B在A左边，所以B是A的左孩子；
继续看先序序列，下一个是D，然后对照中序序列，发现D在A左边，同时在B右边，所以D是B右孩子；
依此类推

img

首先是他们的定义
前序遍历：先访问根节点，再访问左子树，最后访问右子树，即根-左-右。
中序遍历：先访问左子树，再访问根节点，最后访问右子树，即左-根-右。
后序遍历：先访问左子树，再访问右子树，最后访问根节点，即左-右-根。

前序遍历，记住口诀：根左右
中序遍历，记住口诀：左根右
后续遍历，记住口诀：左右根

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7526984
  • 你也可以参考下这篇文章：二叉树的前序遍历，中序遍历，后序遍历
  • 除此之外, 这篇博客: 已知二叉树的前序、中序遍历，求二叉树的后序遍历中的 2.已知二叉树的前序、中序遍历，求二叉树的后序遍历 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

            当我们已知一颗二叉树的前序、中序遍历，或者是中序、后序遍历的结果时，可以重建出该二叉树，而已知前序、后序遍历则无法重建。因此，想要根据二叉树的前序、中序遍历，求得它的后序遍历，只需先将二叉树重建出来，再对其进行后序遍历即可。

            问题的关键在于如何根据二叉树的前序、中序遍历重建出二叉树。这里继续以上文的二叉树为例，它的前序遍历为：1 2 4 7 3 5 6 8、中序遍历为：4 7 2 1 5 3 8 6。注意前序遍历的顺序为根左右，因此它的第一个元素（1）即为二叉树的根结点。知道根结点后，在中序遍历的结果中找到它的位置，中序遍历的顺序为左根右，因此在它左侧的结点即为根结点的左子树，在它右侧的结点即为根结点的右子树，对于子树再进行相同的分析即可。完整过程示例如下：

    1为根结点，在中序遍历中左侧节点有：4 7 2，为它的左子树、右侧结点有：5 3 8 6，为它的右子树；

    对于根结点的左子树4 7 2，前序遍历顺序为2 4 7，因此它的根结点为2，左子树为4 7，无右子树；

    对于左子树4 7，前序遍历顺序为4 7，因此它的根结点为4，无左子树，右子树为7；

    对于右子树7，它无左右子树，是叶子结点。

    对于根结点的右子树5 3 8 6，前序遍历顺序为3 5 6 8，因此它的根结点为3，左子树为5，右子树为8 6；

    对于左子树5，它无左右子树，是叶子结点；

    对于右子树8 6，前序遍历顺序为6 8，因此它的根结点为6，左子树为8，无右子树；

    对于左子树8，它无左右子树，是叶子结点。

    利用递归的思路将以上过程用代码实现，示例如下（利用ArrayList比数组更加方便）：

    public static TreeNode solve(ArrayList<Integer> pre, ArrayList<Integer> vin){
        if(pre.isEmpty()) return null;
        //得到根结点
        int val = pre.get(0);
        TreeNode root = new TreeNode(val);
        //寻找根结点在中序遍历中的位置
        int index = vin.indexOf(val);
        //它左侧的为左子树
        ArrayList<Integer> l_pre = new ArrayList<>(pre.subList(1,index+1));
        ArrayList<Integer> l_vin = new ArrayList<>(vin.subList(0,index));
        root.left = solve(l_pre, l_vin);
        //它右侧的为右子树
        ArrayList<Integer> r_pre = new ArrayList<>(pre.subList(index+1,pre.size()));
        ArrayList<Integer> r_vin = new ArrayList<>(vin.subList(index+1,pre.size()));
        root.right = solve(r_pre, r_vin);
        return root;
}

    得到二叉树后，再对其进行后序遍历 ：

    public static String last_dfs(TreeNode root,StringBuilder s) {
    	if(root.left!=null)	last_dfs(root.left,s);
		if(root.right!=null) last_dfs(root.right,s);
        //最终输出时用trim()方法去除多余的空格
		return s.append(root.val+" ").toString();
}

  • 您还可以看一下 梅会东老师的二级C语言视频教程课程中的 函数的声明、调用、传值(2)小节, 巩固相关知识点
  • 以下回答来自chatgpt:

    可以为二叉树添加更多的详细解释，例如先序遍历、中序遍历和后序遍历的具体定义和实现方法。同时，可以提供已知先序和中序的具体数据来更好地帮助理解。

    针对最长递增子序列问题，可以给出两种解决方法：动态规划和动态规划与二分查找结合。对于动态规划方法，可以给出详细的思路和代码实现；对于动态规划与二分查找结合的方法，可以同样给出清晰易懂的思路和代码实现，来帮助理解这个问题。

    关于二叉树的遍历，以下是三种常见的遍历方式和对应的实现方法：

    1. 先序遍历 先访问根结点，再访问左子树，最后访问右子树。 递归实现：
    public void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

    非递归实现：

    public void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}
    1. 中序遍历 先访问左子树，再访问根结点，最后访问右子树。 递归实现：
    public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

    非递归实现：

    public void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        System.out.print(node.val + " ");
        node = node.right;
    }
}
    1. 后序遍历 先访问左子树，再访问右子树，最后访问根结点。 递归实现：
    public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

    非递归实现：

    public void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");
    }
}

    对于最长递增子序列问题，可以给出动态规划和动态规划与二分查找结合的两种解决方法：

    1. 动态规划 建立一个数组dp，dp[i]记录nums[0:i]的最长递增子序列的长度。 dp[i]=max(dp[j]+1)，j∈{j∣nums[j]<nums[i],0<=j<i} 输出max(dp)即可，时间复杂度O(n^2)，空间复杂度O(n)。
    public int maxLengthCSub(int[] nums) {
    if (nums == null) {
        return 0;
    }
    int len = nums.length;
    if (len == 0 || len == 1) {
        return len;
    }
    int maxLen = 1;
    int[] dp = new int[len];
    for (int i = 0; i < len; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);  // 更新dp[i]
                maxLen = Math.max(maxLen, dp[i]);  // 更新最大值
            }
        }
    }
    return maxLen;
}
    1. 动态规划与二分查找结合 同样建立一个数组dp，但是这里dp记录的是上升子序列，遍历nums数组，用nums的元素填充dp，填充规则是什么呢？首先利用二分查找找到nums[i]在dp中应该插入的位置j，若j==当前dp的长度，则在dp末尾插入nums[i]，maxLen加一，否则dp[j]=nums[i]。时间复杂度O(nlgn)，空间复杂度O(n)。
    public int maxLengthCSub(int[] nums) {
    if (nums == null) {
        return 0;
    }
    if (nums.length == 0 || nums.length == 1) {
        return nums.length;
    }
    int[] dp = new int[nums.length];
    int maxLen = 0;
    for (int i = 0; i < nums.length; i++) {
        int index = findIndex(dp, maxLen, nums[i]);
        dp[index] = nums[i];
        if (index == maxLen) {
            maxLen++;
        }
    }
    return maxLen;
}
// 二分查找，找到target在nums[0:len-1]的插入位置
public int findIndex(int[] nums, int len, int target) {
    if (len == 0) {
        return 0;
    }
    int low = 0;
    int high = len;
    if (target <= nums[low]) {
        return 0;
    }
    if (target > nums[len - 1]) {
        return len;
    }
    while (low < high) {
        int middle = low + (high - low) / 2;
        if (target > nums[middle])  // 右边
            low = middle + 1;
        else
            high = middle;
    }
    return low;
}

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^