porblem description
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
algorithm thought
二叉树的中序遍历问题。这种问题用递归的方法是很简单的。但是还是要知道迭代的写法。毕竟如果节点很多的话，那么多递归函数，栈开销会很大。
递归写法很简单，按顺序访问就行，对于迭代写法，我们首先要明白我们访问的顺序，先左，后中再右。我们使用一个栈保存中间节点，没碰到一个root节点，顺序将左子树一直push进栈，到叶子节点的时候，弹出顶上的节点，这时候就能访问了，然后对于这个节点的右子树，把它当做一个root，继续运行一遍
然后去看了一下discuss，真的是发现每次看都会发现很意想不到的算法。比如中序遍历，这里就可以用morris traversal，只需要O(1)的空间，时间复杂度还是控制在O(n)。极大的减少了空间。这里主要是利用了叶子节点大量的空指针。前面问题使用栈来辅助解决，是因为访问到后续节点的时候，不能够再回到根节点，这里用叶子节点的指针，指向后继节点，方便回到前面。
步骤是：
1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。
code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//递归写法
class Solution {
public:
vector<int> res;
void inorder(TreeNode* root)
{
if(root==NULL)
return;
inorder(root->left);
res.push_back(root->val);
inorder(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
inorder(root);
return res;
}
};
//迭代写法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
while(root||!st.empty()){
while(root){
st.push(root);
root=root->left;
}
root=st.top();
st.pop();
res.push_back(root->val);
root=root->right;
}
return res;
}
};
//morris
lass Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* prev=NULL;
while(root){
if(root->left==NULL){
res.push_back(root->val);
root=root->right;
}else{
prev=root->left;
while(prev->right&&prev->right!=root){
prev=prev->right;
}
if(prev->right==NULL){
prev->right=root;
root=root->left;
}else{
root=prev->right;
prev->right=NULL;
res.push_back(root->val);
root=root->right;
}
}
}
return res;
}
};
algorigthm thought
通过分析和LeetCode最后的结果来说，上面3中方法从上到下应该是越来越好的。迭代对于递归来说，减少了函数栈开销，最后空间用的少一点。Morris对于上面两中来说，只用了O(1)的空间复杂度，最后空间是用的最少的。