/**
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
//返回以root作为根节点的完全二叉树的节点数
int Morris(TreeNode*root){
int res=0;//最终的返回结果
if(root==NULL)
return 0;
TreeNode*cur=root;
while(cur){
TreeNode*mostRight=cur->left;
if(mostRight){//当此时的节点有左子树时,找到左子树上的最右节点
while(mostRight->right&&mostRight->right!=cur){
mostRight=mostRight->right;
}
if(!mostRight->right){//当来到最右节点且是第一次来到cur节点
res++;
mostRight->right=cur;
cur=cur->left;
}
else{//说明此时是第二次来到cur了什么也不做
mostRight->right=NULL;
cur=cur->right;
}
}
else{//说明当前节点没有左子树
res++;
cur=cur->right;
}
}
return res;
}
int nodeNum(struct TreeNode* head) {
return Morris(head);
}
};
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
//现在用Morris遍历重新写一遍(最优解)。时间复杂度O(N),空间复杂度O(1)
//凡是以遍历作为最优解的二叉树题目,Morris遍历都可以作为最优解//返回以root作为根节点的完全二叉树的节点数
int Morris(TreeNode*root){
int res=0;//最终的返回结果
if(root==NULL)
return 0;
TreeNode*cur=root;
while(cur){
TreeNode*mostRight=cur->left;
if(mostRight){//当此时的节点有左子树时,找到左子树上的最右节点
while(mostRight->right&&mostRight->right!=cur){
mostRight=mostRight->right;
}
if(!mostRight->right){//当来到最右节点且是第一次来到cur节点
res++;
mostRight->right=cur;
cur=cur->left;
}
else{//说明此时是第二次来到cur了什么也不做
mostRight->right=NULL;
cur=cur->right;
}
}
else{//说明当前节点没有左子树
res++;
cur=cur->right;
}
}
return res;
}
int nodeNum(struct TreeNode* head) {
return Morris(head);
}
};