day15 二叉树3

110.平衡二叉树

递归法：

class Solution {
public:
    int getHeight(TreeNode *node) {
        if (node == nullptr) {
            return 0;
        }
        return 1 + max(getHeight(node->left), getHeight(node->right));
    }

    bool isBalanced(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        int left = getHeight(root->left);
        int right = getHeight(root->right);
        if (abs(left - right) > 1) {
            return false;
        }
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

迭代法：

class Solution {
public:
    int getDepth(TreeNode* cur) {
        if (cur == nullptr) {
            return 0;
        }
        deque<TreeNode*> q;
        q.push_back(cur);
        int result = 0;
        while (!q.empty()) {
            int n = q.size();
            result ++;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return result;
    }

    bool isBalanced(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop_front();
            int left = getDepth(node->left);
            int right = getDepth(node->right);
            if (abs(left - right) > 1) {
                return false;
            }
            if (node->left) {
                q.push_back(node->left);
            }
            if (node->right) {
                q.push_back(node->right);
            }
        }
        return true;
    }
};

257. 二叉树的所有路径

dfs！

class Solution {
public:
    vector<string> res;
    void getPath(string s, TreeNode *node) {
        s += to_string(node->val);
        if (node->left == nullptr && node->right == nullptr) {
            res.push_back(s);
            return;
        }
        if (node->left) {
            getPath(s + "->", node->left);
        }
        if (node->right) {
            getPath(s + "->", node->right);
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        string s;
        getPath(s, root);
        return res;
    }
};

404.左叶子之和

class Solution {
public:
    int res = 0;
    void getLeft(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        if (cur->left && cur->left->left == nullptr && cur->left->right == nullptr) {
            res += cur->left->val;
        }
        getLeft(cur->left);
        getLeft(cur->right);
    }

    int sumOfLeftLeaves(TreeNode* root) {
        getLeft(root);
        return res;
    }
};

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

class Solution {
public:
    int traversal(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left = traversal(node->left);
        int right = traversal(node->right);
        return 1 + left + right;

    }
    int countNodes(TreeNode* root) {
        return traversal(root);
    }
};