0


【强基计划】LeetCode—根据二叉树的前、中序/中、后序构造二叉树

✨哈喽,进来的小伙伴们,你们好耶!✨

🍅🍅系列专栏:【强基计划】

✈️✈️本篇内容: 根据二叉树的前、中序/中、后序构造二叉树!

⛵⛵作者简介:一名双非本科大三在读的科班Java编程小白,道阻且长,你我同行!

🍱🍱码云存放仓库gitee:Java数据结构全部代码存放!

一、从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

解题思路:

本题要求我们根据前序遍历和中序遍历来构建这颗二叉树,那么思路非常简单。

1、由前序遍历的第一个节点就是根节点root,首先就得到了根节点。

2、那么得到了根节点,我们就去中序遍历的结果里面找到这个根节点,那么这个root的两侧就是我们的左子树和右子树。

3、定义一个i下标遍历前序的结果,那么这个新的节点就是新的左/右子树的根节点,然后在去中序遍历的结果中找到这个新的根节点,同理,它的两侧就是对应的左/右子树。(递归的思想)

代码实现:

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode() {}
  8. * TreeNode(int val) { this.val = val; }
  9. * TreeNode(int val, TreeNode left, TreeNode right) {
  10. * this.val = val;
  11. * this.left = left;
  12. * this.right = right;
  13. * }
  14. * }
  15. */
  16. class Solution {
  17. public int preIndex = 0;
  18. public TreeNode buildTree(int[] preorder, int[] inorder) {
  19. return buildTreeChild(preorder,inorder,0,inorder.length-1);
  20. }
  21. private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
  22. //1、当前根节点是不是还有左子树 或者 右子树
  23. if(inbegin > inend) {
  24. return null;
  25. }
  26. TreeNode root = new TreeNode(preorder[preIndex]);
  27. //2. 找到root再中序遍历的位置
  28. int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
  29. preIndex++;
  30. if(rootIndex == -1) {
  31. return null;
  32. }
  33. //3、构建左子树和右子树
  34. root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
  35. root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
  36. return root;
  37. }
  38. private int findIndex (int[] inorder,int inbegin,int inend,int val) {
  39. for(int i = inbegin;i <= inend;i++) {
  40. if(inorder[i] == val) {
  41. return i;
  42. }
  43. }
  44. return -1;
  45. }
  46. }

运行结果:

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

解题思路:

那么通过上一题我们已经学会了由前序和中序来构造二叉树,那么同理,由中序和后序来构造二叉树也难不倒你,后序的最后一个节点是根节点,然后在中序遍历中找到这个节点,不过后序我们需要先构造右子树,然后才是左子树,因为后序遍历的顺序是左、右、根!

代码实现:

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode() {}
  8. * TreeNode(int val) { this.val = val; }
  9. * TreeNode(int val, TreeNode left, TreeNode right) {
  10. * this.val = val;
  11. * this.left = left;
  12. * this.right = right;
  13. * }
  14. * }
  15. */
  16. class Solution {
  17. public int postIndex = 0;
  18. public TreeNode buildTree(int[] inorder, int[] postorder) {
  19. postIndex = postorder.length-1;
  20. return buildTreeChild(postorder,inorder,0,inorder.length-1);
  21. }
  22. private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
  23. //1、当前根节点是不是还有左子树 或者 右子树
  24. if(inbegin > inend) {
  25. return null;
  26. }
  27. TreeNode root = new TreeNode(postorder[postIndex]);
  28. //2. 找到root再中序遍历的位置
  29. int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
  30. postIndex--;
  31. if(rootIndex == -1) {
  32. return null;
  33. }
  34. //3、构建左子树和右子树
  35. root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
  36. root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
  37. return root;
  38. }
  39. private int findIndex (int[] inorder,int inbegin,int inend,int val) {
  40. for(int i = inbegin;i <= inend;i++) {
  41. if(inorder[i] == val) {
  42. return i;
  43. }
  44. }
  45. return -1;
  46. }
  47. }

运行结果:


本文转载自: https://blog.csdn.net/m0_62426532/article/details/127324389
版权归原作者 辰柒_ 所有, 如有侵权,请联系我们删除。

“【强基计划】LeetCode&mdash;根据二叉树的前、中序/中、后序构造二叉树”的评论:

还没有评论