算法打卡 Day19（二叉树）-平衡二叉树 + 二叉树的所有路径 + 左叶子之和 + 完全二叉树的节点个数

Leetcode 101-平衡二叉树

题目描述

https://leetcode.cn/problems/balanced-binary-tree/description/

解题思路

二叉树节点的深度是指从根节点到该节点的最长简单路径边的条数。

二叉树节点的高度是指从该节点到叶子节点的最长简单路径边的条数。

这道题我们使用递归，采用后序遍历的方法，不断获得左右节点的高度，并在中间节点比较其高度是否符合平衡二叉树的要求

class Solution {
public:
    int getHight(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftHeight = getHight(root->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHight(root->right);
        if (rightHeight == -1) return -1;
        int result;
        if (abs(leftHeight - rightHeight) > 1) result = -1;
        else result = 1 + max(leftHeight , rightHeight); 
        return result;
    }
    bool isBalanced(TreeNode* root) {
        return getHight(root) == -1 ? false : true;
    }
};

Leetcode 257-二叉树的所有路径

题目描述

https://leetcode.cn/problems/binary-tree-paths/description/

解题思路

采用前序算法依次遍历

class Solution {
public:
    void tranversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val);//中
        if (cur->left == nullptr && cur->right == nullptr) {
            string sPath;
            for (int i = 0; i < path.size()-1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) {
            tranversal(cur->left, path, result);
            path.pop_back();//回溯
        }
        if (cur->right) {
            tranversal(cur->right, path, result);
            path.pop_back();//回溯
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string>result;
        vector<int>path;
        if (root == nullptr)return result;
        tranversal(root, path, result);
        return result;
    }
};

Leetcode 404-左叶子之和

题目描述

解题思路

叶子节点的左右子节点都为 nullptr，左叶子节点指的是该叶子节点是父节点的左节点。

采用递归后序遍历的方式解决：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return 0;
        int leftValue = sumOfLeftLeaves(root->left);//左
        if (root->left && root->left->left == nullptr && root->left->right == nullptr) leftValue = root->left->val;
        int rightValue = sumOfLeftLeaves(root->right);//右
        int sum = leftValue + rightValue;//中
        return sum;
    }
};

Leetcode 222-完全二叉树的节点个数

题目描述

解题思路

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

不考虑完全二叉树的特性，仅将其当作普通二叉树，采用后序遍历的代码为：

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftNode = countNodes(root->left);
        int rightNode = countNodes(root->right);
        int sum = leftNode + rightNode + 1;
        return sum;
    }
};

此时我们将所有节点都遍历了一遍，因此时间复杂度为$O(n)$

为了降低时间复杂度，我们可以利用完全二叉树的特性，即对于满二叉树，其节点个数为(2^n-1)，在遍历过程中仅仅遍历两侧的节点，从而可以降低时间复杂度

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 1, rightDepth = 1;
        while (left) {//遍历左侧深度
            left = left->left;
            leftDepth++;
        }
        while (right) {//遍历右侧深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth)return (pow(2, leftDepth) - 1);//如果为满二叉树则根据公式直接计算节点个数
        int leftNum = countNodes(root->left);
        int rightNum = countNodes(root->right);
        int sum = leftNum + rightNum + 1;
        return sum;
    }
};