leetcode94中序遍历 递归+迭代

题目; https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

思路一： 递归遍历 中序遍历 左中右 递归三要素：递归函数的参数和返回值 、确定终止的条件、确定单层递归的逻辑 如果节点不为空 ，遍历左子树，直至遍历结束 将值放入数组中，然后遍历右子树

写法一：

class Solution { public:

vector<int>vec; vector<int> inorderTraversal(TreeNode* root) { if(root) { inorderTraversal(root->left); vec.push_back(root->val); inorderTraversal(root->right); } return vec; }

};

写法二： class Solution { public:

vector<int>vec; vector<int> inorderTraversal(TreeNode* root) { if(root==NULL) return vec; inorderTraversal(root->left); vec.push_back(root->val); inorderTraversal(root->right); return vec; }

};

思路二;迭代实现

中序遍历规则 左右中，先访问中间部的节点，然后一层一层向下访问，直到树左面的最底部，在开始处理节点（也就是把结点的值放到数组里面），这样处理顺序和访问顺序不一样，需要借助指针来访问节点，栈的作用时用来处理结点的 思路 ：从根节点一层一层遍历，进栈，直到数的最左端的节点 将栈顶元素抛出，进数组，然后遍历其右子树，

class Solution { public:

vector<int> inorderTraversal(TreeNode* root) { vector<int>vec; stack<TreeNode*> stk; TreeNode*cur=root; while(!stk.empty()||cur!=NULL) { if(cur!=NULL) { stk.push(cur); cur=cur->left; } else { cur=stk.top(); stk.pop(); vec.push_back(cur->val); cur=cur->right; } } return vec; }

};