Construct Binary Tree from Inorder and Postorder Traversal

Question

  1. Given inorder and postorder traversal of a tree, construct the binary tree.
  3. Example
  4. Given inorder [1,2,3] and postorder [1,3,2], return a tree:
  5.   2
  6.    / \
  7.    1   3
  8.    Note
  9.    You may assume that duplicates do not exist in the tree.

题解

和题 Construct Binary Tree from Preorder and Inorder Traversal 几乎一致，关键在于找到中序遍历中的根节点和左右子树，递归解决。

Java

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  13. public class Solution {
  14.     /**
  15.      *@param inorder : A list of integers that inorder traversal of a tree
  16.      *@param postorder : A list of integers that postorder traversal of a tree
  17.      *@return : Root of a tree
  18.      */
  19.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  20.         if (inorder == null || postorder == null) return null;
  21.         if (inorder.length == 0 || postorder.length == 0) return null;
  22.         if (inorder.length != postorder.length) return null;
  24.         TreeNode root = helper(inorder, 0, inorder.length - 1,
  25.                postorder, 0, postorder.length - 1);
  26.         return root;
  27.     }
  29.     private TreeNode helper(int[] inorder, int instart, int inend,
  30.                             int[] postorder, int poststart, int postend) {
  31.         // corner cases
  32.         if (instart > inend || poststart > postend) return null;
  34.         // build root TreeNode
  35.         int root_val = postorder[postend];
  36.         TreeNode root = new TreeNode(root_val);
  37.         // find index of root_val in inorder[]
  38.         int index = findIndex(inorder, instart, inend, root_val);
  39.         // build left subtree
  40.         root.left = helper(inorder, instart, index - 1,
  41.                            postorder, poststart, poststart + index - instart - 1);
  42.         // build right subtree
  43.         root.right = helper(inorder, index + 1, inend,
  44.                            postorder, poststart + index - instart, postend - 1);
  45.         return root;
  46.     }
  48.     private int findIndex(int[] nums, int start, int end, int target) {
  49.         for (int i = start; i <= end; i++) {
  50.             if (nums[i] == target) return i;
  51.         }
  52.         return -1;
  53.     }
  54. }

源码分析

找根节点的方法作为私有方法，辅助函数需要注意索引范围。

复杂度分析

找根节点近似 O(n), 递归遍历整个数组，嵌套找根节点的方法，故总的时间复杂度为 O(n^2).