Given a binary tree, return theinordertraversal of its nodes' values.
For example:
Given binary tree{1,#,2,3}
,
1
\
2
/
3
return[1,3,2]
.
Note:Recursive solution is trivial, could you do it iteratively?
confused what"{1,#,2,3}"
means?>
read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}"
.
会如何保存这个Vector中间数据,就能解决这道题目了。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> vi;
inHelper(root, vi);
return vi;
}
void inHelper(TreeNode *node, vector<int>& vi)
{
if(node == nullptr) return;
inHelper(node->left, vi);
vi.push_back(node->val);
inHelper(node->right, vi);
}
};
2014-1-9 update iterative的解法,我使用一个标志flag,判断是否遍历过的节点:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
bool flag = false;
while (!stk.empty())
{
if (!flag)
while (stk.top()->left) stk.push(stk.top()->left);
TreeNode *t = stk.top();
rs.push_back(t->val);
stk.pop();
flag = true;
if (t->right)
{
stk.push(t->right);
flag = false;
}
}
return rs;
}
或者如下,leetcode上解说的算法:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
TreeNode *p = root;
while (!stk.empty() || p)
{
if (p)
{
stk.push(p);
p = p->left;
}
else
{
p = stk.top();
stk.pop();
rs.push_back(p->val);
p = p->right;
}
}
return rs;
}
理解了树的操作就好办了,破坏原树的结果输出的程序:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
while (!stk.empty())
{
while (stk.top()->left) stk.push(stk.top()->left);
TreeNode *t = stk.top();
rs.push_back(t->val);
stk.pop();
if (!stk.empty()) stk.top()->left = nullptr;
if (t->right) stk.push(t->right);
}
return rs;
}
//2014-2-14 update
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> rs;
if (!root) return rs;
stack<TreeNode *> stk;
stk.push(root);
while (!stk.empty())
{
while (stk.top()->left) stk.push(stk.top()->left);
TreeNode *t = stk.top();
stk.pop();
if (!stk.empty()) stk.top()->left = nullptr;
rs.push_back(t->val);
if (t->right) stk.push(t->right);
}
return rs;
}
分享到:
相关推荐
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
二叉树中序遍历 :evergreen_tree: 给定一棵二叉树,返回其节点值的中序遍历。 Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 跟进:递归解决方案是微不足道的,你能迭代吗? 中序遍历: 请注意,节点 75 ...
给定一棵二叉树,返回其节点值的中序遍历。 Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] :red_exclamation_mark: :collision: 注意:在不使用递归(隐式使用堆栈)或显式堆栈的情况下实现中序遍历。 :...
94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105....
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
105从Preorder和Inorder Traversal.js构造二叉树 106从有序和后置Traversal.js构造二叉树 107二叉树级订单遍历II.js 108将排序后的数组转换为Binary Search Tree.js 大多数Water.js的11个容器 110平衡Binary Tree....
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 ...
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 ...
中序遍历的迭代实现, 核心操作, POP时,如果有右孩子, 把右孩子的最左一串入栈. 出栈的是, 这个节点的相对角色是个root节点. 所以 出栈时, 左子树已遍历完毕, 然后, root出栈, 再将右子树遍历. 次栈顶元素是刚POP出的...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 ...binary_tree_inorder_traversal binary_tree_level_order_traversal binary_tree_level_order_traversal_I
lru cache leetcode leetcode 数据结构和算法的学习 学习数据结构和算法的好处 ...中序/前序/后续遍历 Linked List 链表 Breadth-first/Depth-first search 广度优先/深度优先搜索 Tree 树/Binary Search T
leetcode 2 和 c Leetcode_questions 目前拥有: ...Inorder Traversal(c++:tree traversal inorder) 100.Same Tree(c++) 101.对称树(c++) 104.二叉树的最大深度(c++) 108.将排序数组转换为二叉搜索树
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 ...binary_tree_inorder_traversal binary_tree_level_order_traversal binary_tree_level_order_traversal_I
Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳...