Question :
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.
Anwser 1 :
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> result(0);
if (root == NULL) return result;
stack<TreeNode *> S;
TreeNode* p = root;
do
{
if (p != NULL) {
S.push(p);
p = p->left;
} else {
p = S.top();
S.pop();
result.push_back(p->val);
p = p->right;
}
}while(!S.empty() || p != NULL);
return result;
}
};
Anwser 2 :
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *p, vector<int> &result)
{
if(p->left != NULL)
dfs(p->left, result);
result.push_back(p->val);
if(p->right!=NULL)
dfs(p->right, result);
}
vector<int> inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TreeNode * head = root;
vector<int> result;
result.clear();
if(head!=NULL) {
dfs(head, result);
}
return result;
}
};
Anwser 3 :
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> result;
result.clear();
stack<TreeNode *> stack_in;
stack<TreeNode *> stack_out;
if(root == NULL) return result;
stack_in.push(root);
while(!stack_in.empty())
{
TreeNode *node_in = stack_in.top();
stack_in.pop();
stack_out.push(node_in);
if(node_in->right!=NULL && node_in->left!=NULL)
{
stack_in.push(node_in->right);
stack_in.push(node_in->left);
} else if(node_in->left!=NULL && node_in->right==NULL) {
stack_in.push(node_in->left);
} else if(node_in->left==NULL && node_in->right!=NULL) {
stack_in.push(node_in->right);
result.push_back(node_in->val);
stack_out.pop();
} else {
result.push_back(node_in->val);
stack_out.pop();
while(!stack_out.empty())
{
TreeNode * tmp = stack_out.top();
stack_out.pop();
result.push_back(tmp->val);
if(tmp->right!=NULL)
break;
}
}
}
return result;
}
};
参考推荐:
Binary Tree Inorder Traversal
分享到:
相关推荐
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
105从Preorder和Inorder Traversal.js构造二叉树 106从有序和后置Traversal.js构造二叉树 107二叉树级订单遍历II.js 108将排序后的数组转换为Binary Search Tree.js 大多数Water.js的11个容器 110平衡Binary Tree....
Inorder Traversal 对于树的问题,大多数我们都会使用递归的方法。原因是树的左子树也是树,右子树也是树,使用递归的方法最简单快捷。这道题是需要我们用Inorder的顺序输出节点。inorder的顺序是先左再自己再右。...
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 ...
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 ...Binary Tree ...Traversal ...Binary Tree Inorder Traversal 318. Maximum Product of Word Length
Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
LeetCode笔记本docsifyjsLeetCode算法Java c / c ++ javascript的基本知识简单的1. Two Sum 704. Classical Binary Search2.... Binary Tree Inorder Traversal144. Binary Tree Preorder Traversal145. Binary Tree
leetcode 2 和 c Leetcode_questions 目前拥有: ...Inorder Traversal(c++:tree traversal inorder) 100.Same Tree(c++) 101.对称树(c++) 104.二叉树的最大深度(c++) 108.将排序数组转换为二叉搜索树
leetcode 树节点 二叉树中序遍历 :evergreen_tree: 给定一棵二叉树,返回其节点值的中序遍历。 Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 跟进:递归解决方案是微不足道的,你能迭代吗? 中序遍历: ...
94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105....
[105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 ...binary_tree_inorder_traversal binary_tree_level_order_traversal binary_tree_level_order_traversal_I
binary-tree-inorder-traversal 无官方题解 104 maximum-depth-of-binary-tree 105 construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-...
Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳...
lru cache leetcode leetcode 数据结构和算法的学习 ...In/Pre/Post-order Traversal 中序/前序/后续遍历 Linked List 链表 Breadth-first/Depth-first search 广度优先/深度优先搜索 Tree 树/Binary Search T