[LeetCode]94.Binary Tree Inorder Traversal

本文主要是介绍[LeetCode]94.Binary Tree Inorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

Given a binary tree, return the inorder traversal 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.

【代码】

/*********************************
*   日期：2014-11-17
*   作者：SJF0115
*   题号: Binary Tree Inorder Traversal
*   来源：https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <malloc.h>
#include <vector>
#include <stack>
using namespace std;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> v;if (root == NULL){return v;}// 根节点入栈stack<TreeNode*> stack;TreeNode* node = root;// 遍历while(node != NULL || !stack.empty()){//遍历左子树if(node != NULL){stack.push(node);node = node->left;}else{//左子树为空，访问右子树node = stack.top();stack.pop();v.push_back(node->val);node = node->right;}}return v;}
};//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){char data;//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树cin>>data;if(data == '#'){T = NULL;}else{T = (TreeNode*)malloc(sizeof(TreeNode));//生成根结点T->val = data-'0';//构造左子树CreateBTree(T->left);//构造右子树CreateBTree(T->right);}return 0;
}int main() {Solution solution;TreeNode* root(0);CreateBTree(root);vector<int> v = solution.inorderTraversal(root);for(int i = 0;i < v.size();i++){cout<<v[i]<<endl;}
}

这篇关于[LeetCode]94.Binary Tree Inorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---