leetCode解题报告之构造二叉树(递归)

港控/mmm° 2022-08-26 03:56 9阅读 0赞

此博文主要讲述了构造二叉树的两种方法：

1、通过先序和中序构造出二叉树( 来自leetCode OJ上的 题目：[Construct Binary Tree from Preorder and Inorder Traversal][] ** **)

2、通过后序和中序构造出二叉树( 来自leetCode OJ上的 题目：[Construct Binary Tree from Inorder and Postorder Traversal][])

这两题的解法类似，下面我来详细讲下如何通过

二叉树的先序序列和中序序列来构造出二叉树，至于后序序列和中序序列就不着重讲了哈！

**题目：**

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:  
You may assume that duplicates do not exist in the tree.

**分析：**

题目要求我们通过中序序列和先序序列来构造出这棵二叉树，返回它的根节点。

那么我们先模拟随便画出一棵二叉树来，再把它的先序，中序，后序全部写出来

![SouthEast][]

**int\[\] preOrder = new int\[\]\{7,-10,-4,3,-1,2,-8,11\};**

**int\[\] postOrder = new int\[\]\{-4,-1,3,-10,11,-8,2,7\};  
int\[\] inOrder = new int\[\]\{-4,-10,3,-1,7,11,-8,2\};**

**解题思路：**

如上，我们得到了一棵二叉树的先序序列preOrder = \{7,-10,-4,3,-1,2,-8,11\};和中序序列inOrder = \{-4,-10,3,-1,7,11,-8,2\};

我们想要构建出这棵二叉树，那么我采用递归的方法来确定出每个结点和结点间的关系

通过先序序列\{7,-10,-4,3,-1,2,-8,11\}，我们可以知道，第一个结点7肯定是二叉树的根结点，而第二个结点-10，有可能是根结点的左子树的根结点，也有可能是右子树的根结点（具体得看中序序列中的 "7" 左边是否还有其他的结点值，或者右边是否还有其他的结点值），居然这个大问题可以被分解成小问题，我们选择采用递归的方式来解决这个问题

1. 首先通过preOrder序列，得到根结点root！

2. 递归求出root的左子树

3. 递归求出root的右子树

4. 将左子树的根结点赋值给root.left,  右子树的根结点赋值给root.right

**AC代码（[Construct Binary Tree from Preorder and Inorder Traversal][] ）:**

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length == 0 || inorder.length == 0)
                return null;
            int len = inorder.length;
            return createTreeNode(preorder,inorder,0,len-1,0);
        }
        
        public TreeNode createTreeNode(int[] preorder, int[] inorder, int inLeft, int inRight, int preIndex){
            //判断是否为叶子结点
            if (inLeft == inRight){
                TreeNode node = new TreeNode(inorder[inLeft]);
                node.left = null;
                node.right = null;
                return node;
            }
            //把preOrder中当前下标preIndex指向的val取出
            int val = preorder[preIndex];
            int findIndex = inLeft;
            //找到val在inOrder中的位置(该子树的根节点位置)
            while (findIndex != inRight && val != inorder[findIndex]){
                findIndex++;
            }
            
            TreeNode leftNode;
            TreeNode rightNode;
            //判断是否有左右子树，并创建出相应的左右子树（如果val在inOrder中的位置下标等于inLeft，表明这个子树是没有左子树的，而val在inOrder中的位置下标等于inRight，表明这个子树没有右子树）
            if (findIndex == inLeft){
                leftNode = null;
            }else{
                leftNode = createTreeNode(preorder,inorder,inLeft,findIndex-1,++preIndex);
            }
            if (findIndex == inRight){
                rightNode = null;
            }else{
                rightNode = createTreeNode(preorder,inorder,findIndex+1,inRight,++preIndex);
            }
            //把左右子树赋值给root结点
            TreeNode root = new TreeNode(val);
            root.left = leftNode;
            root.right = rightNode;
            return root;
        }
    }

**AC代码（[Construct Binary Tree from Inorder and Postorder Traversal][])**

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        private int postIndex;
        public TreeNode buildTree(int[] inorder,int[] postorder) {
            if (postorder.length == 0 || inorder.length == 0)
                return null;
            int len = inorder.length;
            postIndex = postorder.length - 1;
            return createTreeNode(postorder,inorder,0,len-1);
        }
        public TreeNode createTreeNode(int[] inorder, int[] postorder, int inLeft, int inRight){
            if (inLeft == inRight){
                TreeNode node = new TreeNode(inorder[inLeft]);
                node.left = null;
                node.right = null;
                return node;
            }
            int val = postorder[postIndex];
            int findIndex = inLeft;
            while (findIndex != inRight && val != inorder[findIndex]){
                findIndex++;
            }
            TreeNode leftNode;
            TreeNode rightNode;
            
            if (findIndex == inRight){
            	rightNode = null;
            }else{
            	--postIndex;
            	rightNode = createTreeNode(inorder,postorder,findIndex+1,inRight);
            }
            
            if (findIndex == inLeft){
                leftNode = null;
            }else{
                --postIndex;
                leftNode = createTreeNode(inorder,postorder,inLeft,findIndex-1);
            }
            
            TreeNode root = new TreeNode(val);
            root.left = leftNode;
            root.right = rightNode;
            return root;
        }
    }

**博主算法方面比较薄弱，写得不好，欢迎大家给我留言哈！！！**

[Construct Binary Tree from Preorder and Inorder Traversal]: http://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[Construct Binary Tree from Inorder and Postorder Traversal]: http://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[SouthEast]: /images/20220824/00a99e89a5e54eabbcce1ae720ce430d.png