資訊專欄INFORMATION COLUMN
摘要：遞歸法不說了，棧迭代的函數(shù)是利用的原理，從根節(jié)點(diǎn)到最底層的左子樹，依次入堆棧。然后將出的結(jié)點(diǎn)值存入數(shù)組，并對出的結(jié)點(diǎn)的右子樹用函數(shù)繼續(xù)迭代。
Problem
Given a binary tree, return the inorder traversal of its nodes" values.
ExampleGiven binary tree {1,#,2,3},
1
2
/
3
return [1,3,2].
ChallengeCan you do it without recursion?
Note遞歸法不說了，棧迭代的helper函數(shù)是利用stack的LIFO原理，從根節(jié)點(diǎn)到最底層的左子樹，依次push入堆棧。然后將pop出的結(jié)點(diǎn)值存入數(shù)組，并對pop出的結(jié)點(diǎn)的右子樹用helper函數(shù)繼續(xù)迭代。
SolutionRecursion
public class Solution {
public ArrayList inorderTraversal(TreeNode root) {
ArrayList res = new ArrayList();
if (root == null) return res;
helper(root, res);
return res;
}
public void helper(TreeNode root, ArrayList res) {
if (root.left != null) helper(root.left, res);
res.add(root.val);
if (root.right != null) helper(root.right, res);
}
}
Stack Iteration
public class Solution {
public ArrayList inorderTraversal(TreeNode root) {
ArrayList res = new ArrayList();
Stack stack = new Stack();
if (root == null) return res;
helper(stack, root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) helper(stack, cur.right);
}
return res;
}
public void helper(Stack stack, TreeNode root) {
stack.push(root);
while (root.left != null) {
root = root.left;
stack.push(root);
}
}
}
Another Stack Iteration
public class Solution {
public ArrayList inorderTraversal(TreeNode root) {
ArrayList res = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65922.html
摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點(diǎn)在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當(dāng)前進(jìn)到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點(diǎn)之后，要將加，才能進(jìn)行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...
摘要：當(dāng)你被的時(shí)候，人家問，一定要說，當(dāng)然可以啦所以，不用，怎么辦幸好，這是一道的題目，只要逐層遍歷，就可以了。所以，試一試用堆棧的做法吧記得的特點(diǎn)是后入先出哦 Problem Given a binary tree, return the preorder traversal of its nodes values. Example Given: 1 / 2 3 ...
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 / ...
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...
摘要：二分法復(fù)雜度時(shí)間空間思路我們先考察先序遍歷序列和中序遍歷序列的特點(diǎn)。對于中序遍歷序列，根在中間部分，從根的地方分割，前半部分是根的左子樹，后半部分是根的右子樹。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...
閱讀 1424·2021-11-22 09:34
閱讀 1386·2021-09-22 14:57
閱讀 3418·2021-09-10 10:50
閱讀 1408·2019-08-30 15:54
閱讀 3700·2019-08-29 17:02
閱讀 3483·2019-08-29 12:54
閱讀 2622·2019-08-27 10:57
閱讀 3328·2019-08-26 12:24
