資訊專(zhuān)欄INFORMATION COLUMN
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過(guò)，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。
Construct Binary Tree from Inorder and Preorder Traversal Problem
Given preorder and inorder traversal of a tree, construct the binary tree.
NoticeYou may assume that duplicates do not exist in the tree.
ExampleGiven in-order [1,2,3] and pre-order [2,1,3], return a tree:
2 / 1 3Note
許久未更。做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。
這道題目的要點(diǎn)在于找inorder的區(qū)間。preStart每增加一次，就對(duì)應(yīng)一個(gè)新的子樹(shù)。每個(gè)子樹(shù)的根節(jié)點(diǎn)都可以在inorder的中間某處找到，以此為界，左邊是這個(gè)根節(jié)點(diǎn)的左子樹(shù)，右邊是右子樹(shù)。不斷遞歸，得解。
邊界條件需要注意：
若preorder或inorder數(shù)組為空，返回空；
當(dāng)preStart前進(jìn)到超出preorder末位，或inStart超過(guò)inEnd，返回空；
每次創(chuàng)建完根節(jié)點(diǎn)之后，要將preStart加1，才能進(jìn)行遞歸。
Solutionpublic class Solution {
int preStart = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
return helper(preorder, inorder, 0, preorder.length-1);
}
public TreeNode helper(int[] preorder, int[] inorder, int inStart, int inEnd) {
if (preStart >= preorder.length || inStart > inEnd) return null;
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == preorder[preStart]) {
index = i;
break;
}
}
TreeNode root = new TreeNode(preorder[preStart++]);
root.left = helper(preorder, inorder, inStart, index-1);
root.right = helper(preorder, inorder, index+1, inEnd);
return root;
}
}
Construct Binary Tree from Inorder and Postorder Traversal
Problem
Given inorder and postorder traversal of a tree, construct the binary tree.
NoticeYou may assume that duplicates do not exist in the tree.
ExampleGiven inorder [1,2,3] and postorder [1,3,2], return a tree:
2 / 1 3Note
和先序+中序方法一樣，不過(guò)這次是逆推，遞歸的時(shí)候先右子樹(shù)，后左子樹(shù)即可。
Solution Recursionpublic class Solution {
int postEnd;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postEnd = postorder.length - 1;
return helper(postorder, inorder, 0, inorder.length - 1);
}
private TreeNode helper(int[] postorder, int[] inorder, int inStart, int inEnd) {
if (postEnd < 0 || inStart > inEnd) return null;
TreeNode root = new TreeNode(postorder[postEnd--]);
int inMid = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inMid = i;
break;
}
}
root.right = helper(postorder, inorder, inMid +1, inEnd);
root.left = helper(postorder, inorder, inStart, inMid-1);
return root;
}
}
Using Stack
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length < 1) return null;
int i = inorder.length - 1;
int p = i;
TreeNode node;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
Stack stack = new Stack<>();
stack.push(root);
p--;
while (true) {
if (inorder[i] == stack.peek().val) { // inorder[i] is on top of stack, pop stack to get its parent to get to left side
if (--i < 0) break;
node = stack.pop();
if (!stack.isEmpty() && inorder[i] == stack.peek().val) continue;
node.left = new TreeNode(postorder[p]);
stack.push(node.left);
} else { // inorder[i] is not on top of stack, postorder[p] must be right child
node = new TreeNode(postorder[p]);
stack.peek().right = node;
stack.push(node);
}
p--;
}
return root;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65932.html
Problem Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / ...
摘要：解題思路利用遞歸思想，先序遍歷的第一個(gè)元素就是根節(jié)點(diǎn)，然后在中序遍歷中尋找該節(jié)點(diǎn)，該節(jié)點(diǎn)左邊的就是左子樹(shù)，右邊的是右子樹(shù)。 Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. ...
Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...
摘要：這里要注意的是的用法。所以記住，用可以從自動(dòng)分離出數(shù)組。跳過(guò)第一個(gè)元素并放入數(shù)組最快捷語(yǔ)句建立的用意記錄處理過(guò)的結(jié)點(diǎn)并按處理所有結(jié)點(diǎn)和自己的連接下面先通過(guò)判斷，再修改的符號(hào)的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...
摘要：根據(jù)二叉平衡樹(shù)的定義，我們先寫(xiě)一個(gè)求二叉樹(shù)最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹(shù)的差值來(lái)判斷當(dāng)前結(jié)點(diǎn)的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...
閱讀 2906·2021-11-19 09:40
閱讀 5768·2021-09-27 14:10
閱讀 2192·2021-09-04 16:45
閱讀 1637·2021-07-25 21:37
閱讀 3080·2019-08-30 10:57
閱讀 3083·2019-08-28 17:59
閱讀 1129·2019-08-26 13:46
閱讀 1496·2019-08-26 13:27
