题解 | #完全二叉树结点数#

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    //凡是以遍历作为最优解的二叉树题目，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);
    }
};