剑指offer-面试题7

迷南。 2024-04-19 08:21 11阅读 0赞

### 文章目录 ###

*   *  1.基本知识复习
     *  2.面试题7
     *   *  2.1 前序中序生成二叉树
         *  2.2 后序中序生成二叉树
     *  3.小结

## 1.基本知识复习 ##

对于二叉树的前中后序，阅读下面内容：

![format_png][]

*  前序遍历：先访问根节点，再访问左子节点，再访问右子节点。所以上图得到的结果为：10、6、4、8、14、12、16
 *  中序遍历：先访问左子节点，再访问根节点，再访问右子节点。所以上的得到的结果为：4、6、8、10、12、14、16
 *  后序遍历：先访问左子节点，在访问右子节点，再访问跟节点。所以上的得到的结果为：4、8、6、12、16、14、10
 *  宽度优先：先访问树第一层，再访问树第二程……，并且从左往右，故可得到的结果为：10、6、14、4、8、12、16

## 2.面试题7 ##

### 2.1 前序中序生成二叉树 ###

**题目：**

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。例如输入前序遍历序列\{1， 2， 4， 7， 3， 5， 6， 8\}和中序遍历序列\{4， 7， 2， 1，5， 3， 8， 6\}，则重建出二叉树并输出它的头结点。二叉树结点的定义如下：

struct BinaryTreeNode{ 
    	int m_nValue;
    	BinaryTreeNode* m_pLeft;
    	BinaryTreeNode* m_pRight;
    }

**分析：**

（1）前序遍历往往能够最先找到根节点，所以1是主根节点；再看看中序遍历，由于中序遍历主根节点在中间位置被访问，所以主根节点的左边是左子树，主根节点的右边是右子树。所以`{4，7，2，1}`为左子树的部分，`{5，3,8,6}`为右子树的部分，如下图所示。其余同理。

\[外链图片转存失败(img-KbGBKNhR-1568551456839)(https://raw.githubusercontent.com/xfljm/img/master/Img/20190912203917.png)\]

（2）使用方法：递归（注意需要重点分析递归过程中，左子树的起始位置和右子树的起始位置）

**树结构定义：**

public class TreeNode { 
    
        //数据域
        public int data;
        //左指针域
        public TreeNode left;
        //右指针域
        public TreeNode right;
        //构造带有参数的构造方法
        public TreeNode(int data) { 
            this.data = data;
        }
    
        @Override
        public String toString() { 
            return "TreeNode [data=" + data + ", left=" + left + ", right=" + right
                    + "]";
        }
    }

**算法实现：**

public class Demo07 { 
    
        public TreeNode rebuildBinaryTree(int preorder[], int inorder[]){ 
    
            //判断是否为空
            if(null == preorder||null == inorder){ 
                return null;
            }
    
            //核心算法
            TreeNode root = rebuildBinaryTreeCore(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    
            return root;
        }
    
        private TreeNode rebuildBinaryTreeCore(int[] preorder, int startPreorder, int endPreorder, int[] inorder, int startInorder, int endInorder) { 
    
            //1.递归出口
            if (startPreorder>endPreorder || startInorder>endInorder){ 
                return null;
            }
    
            //2.递归条件
            //2.1 首先获取根节点
            TreeNode root = new TreeNode(preorder[startPreorder]);
            for (int i=startInorder;i<=endInorder;i++){ 
    
                if(preorder[startPreorder]==inorder[i]){ 
                    //2.2 递归左子树
                    root.left = rebuildBinaryTreeCore(preorder, startPreorder+1, startPreorder+(i-startInorder),
                            inorder, startInorder, i - 1);
                    //2.3 递归右子树
                    root.right = rebuildBinaryTreeCore(preorder, startPreorder+(i-startInorder)+1, endPreorder,
                            inorder, i + 1, endInorder);
                }
            }
            return root;
        }
    
        
    }

**测试用例：**

public class Demo07 { 
    	
        @Test
        public void fun() { 
            int[] preorder = { 1, 2, 4, 7, 3, 5, 6, 8};
            int[] inorder = { 4, 7, 2, 1, 5, 3, 8, 6};
            TreeNode treeNode = rebuildBinaryTree(preorder, inorder);
            System.out.println(treeNode);
        }
    }

**测试结果：**

TreeNode [data=1, left=TreeNode [data=2, left=TreeNode [data=4, left=null, right=TreeNode [data=7, left=null, right=null]], right=null], right=TreeNode [data=3, left=TreeNode [data=5, left=null, right=null], right=TreeNode [data=6, left=TreeNode [data=8, left=null, right=null], right=null]]]

### 2.2 后序中序生成二叉树 ###

**题目：**

例如输入后序遍历序列\{7，4，2，5，8，6，3，1\}和中序遍历序列\{4， 7， 2， 1，5， 3， 8， 6\}，从而构建出二叉树。

**分析：**

（1）与前序遍历有点相反的地方在于，后序遍历首先看最后一个数据，这个数据就是主根节点（这里是1）；然后再看中序序列，从而判断左右子树。其他类似前序中序生成二叉树。

\[外链图片转存失败(img-AmvKKlse-1568551456843)(https://raw.githubusercontent.com/xfljm/img/master/Img/20190912210324.png)\]

（2）方法：递归（仍然注意左右树递归起始位置）

**算法：**

// 下面是通过后序中序序构建二叉树
    public TreeNode rebuildBinaryTree2(int postorder[], int inorder[]){ 
    
        //判断是否为空
        if(null == postorder||null == inorder){ 
            return null;
        }
    
        //核心算法
        TreeNode root = rebuildBinaryTreeCore2(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
    
        return root;
    }
    
    private TreeNode rebuildBinaryTreeCore2(int[] postorder, int startPostorder, int endPostorder, int[] inorder, int startInorder, int endInorder) { 
    
        //1.递归出口
        if (startPostorder>endPostorder || startInorder>endInorder){ 
            return null;
        }
    
        //2.递归条件
        //2.1 首先获取根节点
        TreeNode root = new TreeNode(postorder[endPostorder]);
        for (int i=startInorder;i<=endInorder;i++){ 
    
            if(postorder[endPostorder]==inorder[i]){ 
                //2.2 递归左子树
                root.left = rebuildBinaryTreeCore2(postorder, startPostorder, startPostorder+(i-startInorder)-1,
                                                   inorder, startInorder, i - 1);
                //2.3 递归右子树
                root.right = rebuildBinaryTreeCore2(postorder, startPostorder+(i-startInorder), endPostorder-1,
                                                    inorder, i + 1, endInorder);
            }
        }
        return root;
    }

## 3.小结 ##

这个算法题是二叉树中常见的算法题，其中对于树结构需要熟练使用递归算法来解决相关问题。另外本中觉得最难理解的地方就是在递归左右二叉树时，对左右二叉树位置的判断需要认真分析。

**参考资料：**

*  剑指offer（第二版）
 *  [不贰者-重建二叉树（java）][-_java]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3hmbGptL2ltZy9tYXN0ZXIvSW1nLzIwMTkwOTEyMTkxODM1LnBuZw?x-oss-process=image/format,png
[-_java]: https://blog.csdn.net/u013132035/article/details/80519895#commentBox