本文共 1203 字,大约阅读时间需要 4 分钟。
Given a binary tree, return the inorder traversal of its nodes' values.For example:Given binary tree { 1,#,2,3}, 1 \ 2 / 3return [1,3,2].Note: Recursive solution is trivial, could you do it iteratively?
不断访问其左子树,然后输出其根,然后访问其接着的右子树,重复过程
实现代码如下:
#include#include #include #include using namespace std;struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public: vector inorderTraversal(TreeNode *root) { vector v; if (root == NULL){ return v; } // 根节点入栈 stack 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;}
转载地址:http://kxuoi.baihongyu.com/