LeetCode 剑指 Offer 07. 重建二叉树

r囧r小猫 2022-11-09 14:24 98阅读 0赞

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出
    
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树：
    
        3
       / \
      9  20
        /  \
       15   7
     
    
    限制：
    
    0 <= 节点个数 <= 5000
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：  
首先要了解前序遍历和中序遍历的特点：

*  前序遍历：先对根结点，再访问左子树，最后访问右子树；
 *  中序遍历：先访问左子树，再访问根结点，最后访问右子树；

根据二者的访问次序的不同，我们可以知道前序遍历的节点，在中序遍历结果中，可以将树分为左右子树。  
以例子而言：

前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    在前序遍历第一个数3，为根结点，再看3在中序遍历中位置，3的左边为左子树，右边为结点3的右子树；
    同理可以得到9,20等的子树情况都有哪些数值。

所以我们可以考虑使用递归的方式来重建二叉树：

1.  遍历前序遍历，对前序遍历的每个结点寻找其在中序遍历中位置index；
2.  此时我们可以得到inorder【index】为根结点，而从begin到index-1区间为该根结点的左子树，从index+1到end区间为该根结点的右子树，由此进行递归；
3.  将递归完的根结点逐步返回，最终即可从建完二叉树。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    	int preIndex=0;
    	public TreeNode buildTree(int[] preorder, int[] inorder) {
        
    		return buildTreeNode(preorder, inorder, 0, preorder.length-1);
    	}
    	public TreeNode buildTreeNode(int[] preorder,int[] inorder,int begin,int end) {
        
    		if(begin>end) return null;
    		if(begin==end) {
        
    			TreeNode treeNode=new TreeNode(preorder[preIndex]);
    			preIndex++;
    			return treeNode;
    		}
    		int index=0;
    		for(int i=begin;i<=end;i++) {
        
    			if(inorder[i]==preorder[preIndex]) {
        
    				index=i;
    				break;
    			}
    		}
    		TreeNode treeNode=new TreeNode(preorder[preIndex]);
    		preIndex++;
    		treeNode.left=buildTreeNode(preorder, inorder,begin,index-1);
    		treeNode.right=buildTreeNode(preorder, inorder, index+1, end);
    		return treeNode;
    	}
    }