12.03 二叉树简单题2

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

思路：可以采用深度优先遍历，将每个节点的val放进当前path，然后判断当前节点是否为叶子节点，叶子节点则保存当前路径，非叶子节点则继续遍历

细节：这里findPath的参数path不能用引用，因为引用会将有效的路径也push进了一些无效的val，后续还要加入裁剪path。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void findPaths(TreeNode* root, string path, vector<string>& ret) {
        if (root != nullptr) {
            path += to_string(root->val);
            //判断是否为叶子节点
            if (root->left == nullptr && root->right == nullptr) {  
                ret.push_back(path);                              
            } else {
                path += "->";  
                findPaths(root->left, path, ret);
                findPaths(root->right, path,  ret);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ret;
        findPaths(root, "", ret);
        return ret;
    }
};

222. 完全二叉树的节点个数 

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

思路1：所有节点正常遍历一遍并计数即可。

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

该方法参考了代码随想录

代码随想录 (programmercarl.com)  

思路2：满二叉树有个特点是，只有最后一层可能不是满的且从左到右不会有“间断”。从左右子树来看，只有一个子树不是完全满二叉树。对于完全满二叉树可以按2**h-1得到节点数，对于不是完全满二叉树的可以一直递归左右子树直到出现空节点或叶子节点。

        判断是否为完全满二叉树可以判断 left到底和right到底 两数是否相等。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        //左右子树中最多只有一个子树不是满二叉。

        //该节点为空或叶子节点
        if(!root) return 0;
        else if(!root->left&&!root->right) return 1;
        else{
            int left=0,right=0;
            for(TreeNode* node=root;node;node=node->left) left++;
            for(TreeNode* node=root;node;node=node->right) right++;
            if(left==right) return (1<<left)-1;
            else return countNodes(root->left)+countNodes(root->right)+1;
        }
    }
};

左右子树中最多只有一个子树不是满二叉。所以总体的时间复杂度仍然是logn ^ 2