欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的中序遍历——迭代算法

程序员文章站 2022-06-17 19:54:24
...

题目

二叉树的中序遍历——迭代算法

思路

中序遍历的思想是:左子树——根节点——右子树
所以相应的思路为:

  1. 不断寻找左子树根节点
  2. 当该左子树为空时,输出该节点
  3. 遍历右子树

相应代码如下:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
		stack<TreeNode*> s;
		TreeNode* tre = root;
		while (tre || !s.empty()) {
			while (tre) {//不断寻找左节点
				s.push(tre);
				tre = tre->left;
			}
			//当左子树为空时,则将该节点从栈中弹出
			tre = s.top();
			s.pop();
			v.push_back(tre->val);
			tre = tre->right;//最后遍历右子树
		}
		return v;
    }
};
相关标签: LeetCode