【牛客 - 剑指offer】JZ7 重建二叉树 Java实现 两种方案(递归+非递归stack)

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 树 - JZ7 重建二叉树

题目

题目的主要信息

• 根据二叉树的前序和中序遍历序列，重建该二叉树，并返回根节点

• 两个遍历都没有重复的元素

方案一 递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能将原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一棵完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

对于二叉树的前序遍历，第一个元素必定是二叉树的根节点，因为序列没有重复的元素，因此，中序遍历中可以找到相同的这个元素，并且中序遍历顺序中，根节点将将二叉树分为左右子树两部分

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
首先看前序遍历，1是根节点
在中序遍历中查找1的位置，1左边的都在根节点的左子树，即{4,7,2}在左子树；1右边的都在根节点的右子树，即{5,3,8,6}在右子树
前序遍历中也分为了{2,4,7}和{3,5,6,8}
2位于这个前序遍历中子集的第一位，说明2是左子树的根节点
在{4,7,2}这一中序遍历中，{4,7}都在2的左边，即{4,7}都是以2为根的左子树上的节点
3位于这个前序遍历中子集的第一位，说明3是右子树的根节点
在{5,3,8,6}这一中序遍历中，5位于3的左边，{8,6}位于3的右边，说明，5是3的左子节点，{8,6}都位于3的右子树
…
按照这种思路，依次类推可以得到二叉树的结构如下图

具体做法

1. 先根据前序遍历第一个点建立根节点

2. 然后遍历中序遍历找到根节点在数组中的位置

3. 再按照子树的节点数，将两个遍历序列分割成子数组，将子数组送入函数建立子树

4. 直到子树的序列长度为0，结束递归

import java.util.*;

/**
 * Definition for binary tree
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        int preLength = pre.length;
        int vinLength = vin.length;
        if (preLength == 0 || vinLength == 0) {
            return null;
        }
        //构建根节点
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < vin.length; i++) {
            //在中序遍历中找到pre[0]
            if (vin[i] == pre[0]) {
                //Arrays.copyOfRange(arr,from,to)
                //[from,to)
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i));

                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, preLength), Arrays.copyOfRange(vin, i + 1, vinLength));
                break;
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

方案二 非递归 用栈实现

栈，是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底

• 元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素

• 元素出栈指的是从一个栈删除元素又称作出栈或退栈，他是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

思路

除了递归， 我们可以使用类似非递归前序遍历的方式建立二叉树，利用栈辅助进行非递归，然后依次建立节点。

具体做法

1. 首先前序遍历第一个数组依然是根节点，并建立栈辅助遍历

2. 开始判断，前序遍历中相邻的两个数字有以下几种可能的情况：

   • 前序遍历中后一个节点是前一个节点的左子节点

   • 前序遍历中后一个节点是前一个节点的右子节点

   • 前序遍历中后一个节点是前一个节点的祖先的右子节点

3. 同时遍历pre和vin，判断是否是左子节点

   • 如果是左子节点，则不断深入，用栈记录祖先

   • 如果不是左子节点，需要弹出栈回到相应的祖先，然后进入右子树，整个过程类似非递归前序遍历

自己的一些理解

1. for循环中i指向的节点，表示为当前节点
2. cur变量用来存储当前节点的上一个节点
3. cur之前的父节点、祖先节点都存放在stack中
4. 如果vin[j]和cur不一样，则说明，i节点是cur的左子节点
5. 如果vin[j]和cur一样，表示cur已经是最左下的一个节点，i指向的节点可能是cur或者是cur祖先的右子节点
6. cur和vin[j]一样，j向后移动一个位置，再看vin[j]和栈顶元素是否相等
   • 如果不等，则说明i指向的节点是cur的右子节点
   • 如果相等，弹出栈顶元素，并把cur赋值为栈顶元素，再次比较，看新的栈顶元素是否与vin[j]相同，如果不等，i指向的节点就是cur的右子节点，如果相等，继续while循环…

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0)
            return null;
        Stack<TreeNode> s = new Stack<>();
        //首先建立前序第一个即根节点
        TreeNode root = new TreeNode(pre[0]);
        TreeNode cur = root;
        for(int i = 1, j = 0; i < n; i++){
            //要么旁边这个是它的左节点
            //没有和vin[j]相等说明，还没有深入到最左下节点
            //判断是否是左子节点，如果是左子节点，则不断深度，用栈记录祖先
            if(cur.val != vin[j]){
                cur.left = new TreeNode(pre[i]);
                s.push(cur);
                //要么旁边这个是它的右节点，或者祖先的右节点
                cur = cur.left;
            }else{
                //如果不是左子节点，则需要弹出栈回到相应的祖先，然后进入右子树
                //j++的操作，跳过了根节点
                j++;
                //弹出到符合的祖先
                while(!s.isEmpty() && s.peek().val == vin[j]){
                    cur = s.pop();
                    j++;
                }
                //添加右节点
                cur.right = new TreeNode(pre[i]);
                cur = cur.right;
            }
        }
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39