Binary Tree Inorder Traversal

2019-11-06 07:29:30

字体：大中小

来源：转载

供稿：网友

问题描述：

给定一棵二叉树，返回它的中序遍历。

解题思路：

中序遍历的法则：遍历左子树访问当前元素遍历右子树根据中序遍历的法则，可以得到相应的算法：声明一个栈用来存储还没遍历到的节点，而且从栈顶到栈底是向根部回推的一个过程声明一个遍历指针ptr并赋值为root对于每个节点 if有左子树将该节点压入栈 ptr更新为该节点的左子树 else 无左子树访问该节点值 if有右子树 ptr更新为该节点的右子树 else 无右子树（是树叶）如果栈空则结束 while栈不空访问栈顶元素并判断有无右子树 if无右子树则弹出栈顶元素 else 跳出循环 if栈空则结束 else ptr更新为栈顶元素的右子树并弹出栈顶元素

源代码如下：

class Solution {

public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode* > stk; TreeNode* ptr=root; if(ptr==NULL) return result; while(true) { if(ptr->left!=NULL) { stk.push(ptr); ptr=ptr->left; } else if(ptr->right!=NULL) { result.push_back(ptr->val); ptr=ptr->right; } else { result.push_back(ptr->val); if(stk.empty()) break; else { while(!stk.empty()) { result.push_back(stk.top()->val); if(stk.top()->right==NULL) stk.pop(); else break; } if(stk.empty()) break; else { ptr=stk.top()->right; stk.pop(); } } } } return result; }};

上一篇：uva 147 Dollars （dp）

下一篇：LeetCode 18 4Sum