[LeetCode] 根据中序和后序序列重建二叉树

待我称王封你为后i 2022-08-04 09:18 108阅读 0赞

LeetCode 链接： [根据中序和后序序列重建二叉树][Link 1]

思路：主要在于左右子树根节点的寻找过程  
1、右子树根节点为 postorder 向量容器中根节点的前一个数，故递归时为postorder 的 (index - 1)；  
2、左子树的根节点为 当前 inorder 向量区间内在 postorder 向量容器中出现的最晚的数，故寻找到该索引为postorder 的 tmp ；  
3、特殊情况：只有左子树和只有右子树，该情况下 postorder 的下标均为  (index - 1)  。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            return btConstruct(inorder, postorder, postorder.length - 1, 0, inorder.length - 1) ;
        }
    	
    	public TreeNode btConstruct(int[] inorder, int[] postorder, int index, int l, int r) {
    		
    		if(index < 0 || l > r) {
    			return null ;
    		}
    		
    		TreeNode root = new TreeNode(postorder[index]) ;
    		
    		if(l == r) {
    		    root.left = null ;
    		    root.right = null ;
    		    return root ;
    		}
    		
    		int j ;
    		for(j = l; j <= r; j ++) {
    			if(postorder[index] == inorder[j]) {
    				break ;
    			}
    		}
    		
    		if(j <= r) {
    			if(j == r) { // 只有左子树情况
    				root.left = btConstruct(inorder, postorder, index - 1, l, j - 1) ;
    				root.right = null ;
    			} else if(j == l) { // 只有右子树情况
    				root.right = btConstruct(inorder, postorder, index - 1, j + 1, r) ;
    				root.left = null ;
    			} else {
    				int tmp = -1 ;
    				for(int i = l; i < j; i ++) { // 寻找指定范围[l, j)内 inorder 在postorder中出现的最晚的 tmp 
    					for(int k = 0; k < postorder.length; k ++) {
    						if(inorder[i] == postorder[k] && k > tmp) {
    							tmp = k ;
    						}
    					}
    				}
    				root.left = btConstruct(inorder, postorder, tmp, l, j - 1) ;
    				root.right = btConstruct(inorder, postorder, index - 1, j + 1, r) ;
    			}
    		}
    		
    		return root ;
    	}
    }

[Link 1]: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/