根据后序集合找到根,再根据根,在中序集合中找到索引号,采用递归的构建子树的方法
/** * Definition for binary tree * 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 gT(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1); } private TreeNode gT(int[] inorder, int inStart, int inEnd, int[] postorder, int pStart, int pEnd){ if(inorder==null || postorder==null || inorder.length==0 || postorder.length==0 || inStart>inEnd || pStart>pEnd){ return null; } int childRootVal = postorder[pEnd]; TreeNode childRoot = new TreeNode(childRootVal); int childRootInOrderIndex = -1; for(int i=inStart; i<=inEnd; i++){ if(inorder[i]==childRootVal){ childRootInOrderIndex=i; break; } } if(childRootInOrderIndex==-1){ return null; } int duration = childRootInOrderIndex-inStart; childRoot.left=gT(inorder, inStart, childRootInOrderIndex - 1, postorder, pStart, pStart + duration - 1); childRoot.right=gT(inorder, childRootInOrderIndex+1,inEnd, postorder, pStart+duration, pEnd-1); return childRoot; } }
相关推荐
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
lru缓存leetcode LeetCode_Note leetcode 个人笔记 ...[106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
leetcode 跳跃 Algorithm 算法题解: 包括书籍算法, 程序员算法面试指南, 还有leetcode算法题 ...construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
Inorder 0099 Recover Binary Search Tree - Java Recursive 0101 Symmetric tree - Java Recursive - Java Iterative - C Recursive - Python Iterative 0102 Binary Tree Level Order Traversal - Python3 ...
201 | [Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | [C++](./C++/bitwise-and-of-numbers-range.cpp) [Python](./Python/bitwise-and-of-numbers-range.py) | _...
Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree ...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 树节点 二叉树中序遍历 :evergreen_tree: 给定一棵二叉树,返回其节点值的中序遍历。 Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 跟进:递归解决方案是微不足道的,你能迭代吗? 中序遍历: ...
binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...
leetcode的题目:Balanced Binary Tree
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree Level Order Traversal 103 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level ...
java lru leetcode 算法练习刷题的仓库 理论基础:熟悉常见的数据结构、起码看过一本算法入门书 开始 git clone ...cd ...InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi
leetcode-tag-Tree