立志重刷代码随想录60天冲冲冲！！——第十五天

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

直写了通用方法。

class Solution {
public:
    int TreeNodeNum(TreeNode* node) {
        if (node == nullptr) return 0;

        // 后序遍历！！左右中
        int leftnum = TreeNodeNum(node->left);
        int rightnum = TreeNodeNum(node->right);
        int sum = leftnum + rightnum + 1;

        return sum;
    }

    int countNodes(TreeNode* root) {
        int res = TreeNodeNum(root);
        return res;
    }
};

110.平衡二叉树

后序

若高度为-1，则一直返回-1

逻辑判断：若绝对值大于1，返回-1；否则返回左右高度的最大值➕1

class Solution {
public:
    int getheight(TreeNode* node) {
        // 后序 左右中，重点看“中”的逻辑
        if (node ==nullptr) return 0;
        int leftheight = getheight(node->left);
        if (leftheight == -1) return -1;
        int rightheight = getheight(node->right);
        if (rightheight == -1) return -1;

        int results;
        if (abs(leftheight - rightheight) > 1) return -1;
        else {
            results = max(leftheight, rightheight) + 1;
        }
        return results;
    }
    bool isBalanced(TreeNode* root) {
        int height = getheight(root);
        return height >= 0 ? true: false;
    }
};

257. 二叉树的所有路径

用到回溯

需要注意：先把“中”推入，保证第一个节点进入结果

class Solution {
public:
    void traversal (TreeNode* node, vector<int>& path, vector<string>& results) {
        path.push_back(node->val); // 中
        if (node->left == nullptr && node->right == nullptr) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path.back());
            results.push_back(sPath);
            return;
        }

        if (node->left) {
            traversal(node->left, path, results);
            path.pop_back(); // pop_back()
        }
        if (node->right) {
            traversal(node->right, path, results);
            path.pop_back();
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> results;
        traversal(root, path, results);
        return results;
    }
};

404.左叶子之和

可以不写副函数

左孩子存在，左孩子的左孩子不存在，左孩子的右孩子不存在：left = node->left->val;

class Solution {
public:
    int GetLeft (TreeNode* node) {
        if (node == nullptr) return 0;

        int left = GetLeft(node->left);
        if (node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr) {
            left = node->left->val;
        }
        int right = GetLeft(node->right);
        int sum = left + right;
        return sum;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        int sum = GetLeft(root);
        return sum;
    }
};