{"id":45476,"date":"2023-12-11T15:05:56","date_gmt":"2023-12-11T07:05:56","guid":{"rendered":"https:\/\/wx.kaifamiao.info\/?p=45476"},"modified":"2023-12-11T15:05:56","modified_gmt":"2023-12-11T07:05:56","slug":"%e7%ae%97%e6%b3%95%e9%a2%98%ef%bc%8c%e7%bb%99%e5%89%8d%e5%ba%8f%e5%92%8c%e4%b8%ad%e5%ba%8f%ef%bc%8c%e6%b1%82%e5%87%ba%e4%ba%8c%e5%8f%89%e6%a0%91-2","status":"publish","type":"post","link":"http:\/\/wx.kaifamiao.info\/index.php\/2023\/12\/11\/%e7%ae%97%e6%b3%95%e9%a2%98%ef%bc%8c%e7%bb%99%e5%89%8d%e5%ba%8f%e5%92%8c%e4%b8%ad%e5%ba%8f%ef%bc%8c%e6%b1%82%e5%87%ba%e4%ba%8c%e5%8f%89%e6%a0%91-2\/","title":{"rendered":"\u7b97\u6cd5\u9898\uff0c\u7ed9\u524d\u5e8f\u548c\u4e2d\u5e8f\uff0c\u6c42\u51fa\u4e8c\u53c9\u6811"},"content":{"rendered":"

“`”<\/p>\n

\u53c2\u8003\u56de\u7b54\uff1a<\/p>\n

<pre><code>class TreeNode {
\n int val;
\n TreeNode left;
\n TreeNode right;
\n TreeNode(int x) {
\n val = x;
\n }
\n}
\npublic class TestRecoverBinaryTree {
\n public TreeNode reConstructBinaryTree(int [] preOrder,int [] inOrder)
\n {
\n int pLen = preOrder.length;
\n int iLen = inOrder.length;
\n if(pLen==0 && iLen==0)
\n {
\n return null;
\n }
\n return btConstruct( preOrder, inOrder, 0, pLen-1,0, iLen-1);
\n }
\n \/\/\u6784\u5efa\u65b9\u6cd5\uff0cpStart\u548cpEnd\u5206\u522b\u662f\u524d\u5e8f\u904d\u5386\u5e8f\u5217\u6570\u7ec4\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\u548c\u6700\u540e\u4e00\u4e2a\u5143\u7d20\uff1b
\n \/\/iStart\u548ciEnd\u5206\u522b\u662f\u4e2d\u5e8f\u904d\u5386\u5e8f\u5217\u6570\u7ec4\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\u548c\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u3002
\n public TreeNode btConstruct(int[] preOrder, int[] inOrder, int pStart, int pEnd,int iStart,int iEnd)
\n {
\n \/\/\u5efa\u7acb\u6839\u8282\u70b9
\n TreeNode tree = new TreeNode(preOrder[pStart]);
\n tree.left = null;
\n tree.right = null;
\n if(pStart == pEnd && iStart == iEnd)
\n {
\n return tree;
\n }
\n int root = 0;
\n \/\/\u627e\u4e2d\u5e8f\u904d\u5386\u4e2d\u7684\u6839\u8282\u70b9<\/p>\n

for(root=iStart; root<iEnd; root++)
\n {
\n if(preOrder[pStart] == inOrder[root])
\n {
\n break;
\n }
\n }
\n \/\/\u5212\u5206\u5de6\u53f3\u5b50\u6811<\/p>\n

int leftLength = root – iStart;\/\/\u5de6\u5b50\u6811
\n int rightLength = iEnd – root;\/\/\u53f3\u5b50\u6811<\/p>\n

\/\/\u904d\u5386\u5de6\u5b50\u6811
\n if(leftLength>0)
\n {
\n tree.left = btConstruct(preOrder, inOrder, pStart+1, pStart+leftLength, iStart, root-1);
\n }
\n \/\/\u904d\u5386\u53f3\u5b50\u6811
\n if(rightLength>0)
\n {
\n tree.right = btConstruct(preOrder, inOrder, pStart+leftLength+1, pEnd, root+1, iEnd);
\n }
\n return tree;
\n }
\n}<\/p>\n

<\/code><\/pre><\/p>\n

\u00a0<\/p>\n

<pre><code> "“`
\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"

“`” \u53c2\u8003\u56de\u7b54\uff1a <pre><code>class Tree […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-45476","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/comments?post=45476"}],"version-history":[{"count":1,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45476\/revisions"}],"predecessor-version":[{"id":45477,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45476\/revisions\/45477"}],"wp:attachment":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/media?parent=45476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/categories?post=45476"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/tags?post=45476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}