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

该题目可以用二叉树的Morris遍历来实现空间复杂度为o(1),时间复杂度为o（n）
/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        if(head == nullptr)
            return 0;
        int count = 0;
        TreeNode* cur = head;
        TreeNode* mostRight;
        while(cur){
            if(cur->left){
                mostRight = cur->left;
                while(mostRight->right != nullptr && mostRight->right != cur){		//mostRight表示当前节点的左子树的最右节点
                    mostRight = mostRight->right;
                }
                if(mostRight->right == nullptr){		//如果是第一次到达，则将最右节点的右指针指向当前节点，然后cur指向左孩子
                    mostRight->right = cur;
                    cur = cur->left;
                    continue;
                }else{
                    mostRight->right = nullptr;		//如果是第二次到达，则将最右节点的右孩子恢复nullptr
                }
            }
            count++;
            cur = cur->right;//左子树为空时，则当前节点向右指向

            
        }
        return count;
    }
};