首页 > 代码库 > LeetCode: Binary Tree Inorder Traversal
LeetCode: Binary Tree Inorder Traversal
LeetCode: 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 / 3return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
地址：https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
算法：要求用非递归来进行中序遍历。初始时，从根节点开始，一直往左走，并把每个节点入栈。在while循环内，取栈顶元素，出栈，访问该元素，若该元素有右孩子，往右走，在一直往左走到低并把每个节点进栈，如此循环知道栈为空。代码：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 vector<int> inorderTraversal(TreeNode *root) {13 vector<int> result;14 if(!root) return result;15 TreeNode *p = root;16 stack<TreeNode*> stk;17 while(p){18 stk.push(p);19 p = p->left;20 }21 while(!stk.empty()){22 p = stk.top();23 stk.pop();24 result.push_back(p->val);25 p = p->right;26 while(p){27 stk.push(p);28 p = p->left;29 }30 }31 return result;32 }33 };
LeetCode: Binary Tree Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。