106. 从中序与后序遍历序列构造二叉树

image.png
理论知识简单，如何实现

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组

  • 第六步：递归处理左区间和右区间

    1. class Solution {
    2.   public TreeNode buildTree(int[] inorder, int[] postorder) {
    3.       return buildFromInPost(inorder, 0, inorder.length, postorder, 0, postorder.length);
    4.   }
    6.   public TreeNode buildFromInPost(int[] inorder, int inLeft, int inRight,
    7.                             int[] postorder, int postLeft, int postRight){
    8.       if (postRight == postLeft) {
    9.           return null;
    10.       }
    11.       //后序数组postorder里最后一个即为根结点
    12.       int rootVal = postorder[postRight - 1];
    13.       TreeNode root = new TreeNode(rootVal);
    14.       if (postRight - postLeft == 1) {
    15.           return root;
    16.       }
    17.       //在中序数组inorder中找到根结点值所在的位置
    18.       int rootIndex = 0;
    19.       for (rootIndex = inLeft; rootIndex < inRight; ++rootIndex) {
    20.           if (inorder[rootIndex] == rootVal) {
    21.               break;
    22.           }
    23.       }
    24.       //根据rootIndex划分左右子树继续递归
    25.       root.left = buildFromInPost(inorder, inLeft, rootIndex,
    26.               postorder, postLeft, postLeft + (rootIndex - inLeft));
    27.       root.right = buildFromInPost(inorder, rootIndex + 1, inRight,
    28.               postorder, postLeft + (rootIndex - inLeft), postRight - 1);
    29.       return root;
    30.   }
    31. }

    105. 从前序与中序遍历序列构造二叉树

    把四个区间搞清楚这个题就写完一半了

    1. class Solution {
    2.   public TreeNode buildTree(int[] preorder, int[] inorder) {
    3.       return buildFromPreIn(preorder, 0, preorder.length,
    4.               inorder, 0, inorder.length);
    5.   }
    7.   public TreeNode buildFromPreIn(int[] preorder, int preLeft, int preRight,
    8.                             int[] inorder, int inLeft, int inRight){
    9.       if (preRight == preLeft) {
    10.           return null;
    11.       }
    12.       //前序数组preorder里第一个即为根结点
    13.       int rootVal = preorder[preLeft];
    14.       TreeNode root = new TreeNode(rootVal);
    15.       if (preRight - preLeft == 1) {
    16.           return root;
    17.       }
    18.       //在中序数组inorder中找到根结点值所在的位置
    19.       int rootIndex = 0;
    20.       for (rootIndex = inLeft; rootIndex < inRight; ++rootIndex) {
    21.           if (inorder[rootIndex] == rootVal) {
    22.               break;
    23.           }
    24.       }
    25.       //根据rootIndex划分左右子树继续递归
    26.       //左闭右开区间
    27.       root.left = buildFromPreIn(preorder, preLeft + 1, preLeft + 1 +(rootIndex - inLeft),
    28.               inorder, inLeft, rootIndex);
    29.       root.right = buildFromPreIn(preorder, preLeft + 1 + (rootIndex - inLeft), preRight,
    30.               inorder, rootIndex + 1, inRight);
    31.       return root;
    32.   }
    33. }

    654. 最大二叉树

    1. class Solution {
    2.   public TreeNode constructMaximumBinaryTree(int[] nums) {
    3.       return buildTree(nums, 0, nums.length);
    4.   }
    6.   public TreeNode buildTree(int[] nums, int left, int right) {
    7.       if (right == left) {
    8.           return null;
    9.       }
    10.       int rootVal = Integer.MIN_VALUE;
    11.       int rootIndex = 0;
    12.       for (int i = left; i < right; ++i) {
    13.           if (nums[i] > rootVal) {
    14.               rootVal = nums[i];
    15.               rootIndex = i;
    16.           }
    17.       }
    18.       TreeNode root = new TreeNode(rootVal);
    19.       root.left = buildTree(nums, left, rootIndex);
    20.       root.right = buildTree(nums, rootIndex + 1, right);
    21.       return root;
    22.   }
    23. }

    617. 合并二叉树

    递归法，修改原树的结构

    1.   public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    2.       if (root1 == null) return root2;
    3.       if (root2 == null) return root1;
    4.       root1.val += root2.val;
    5.       root1.left = mergeTrees(root1.left, root2.left);
    6.       root1.right = mergeTrees(root1.right, root2.right);
    7.       return root1;
    8.   }

    递归法，不修改原树的结构

    1.   public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    2.       if (root1 == null) return root2;
    3.       if (root2 == null) return root1;
    4.       TreeNode root  = new TreeNode(root1.val + root2.val);
    5.       root.left = mergeTrees(root1.left, root2.left);
    6.       root.right = mergeTrees(root1.right, root2.right);
    7.       return root;
    8.   }