算法训练day17 LeetCode 110.257.404

110平衡二叉树

题目

110. 平衡二叉树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

当子树已经不平衡，直接返回-1.平衡则返回子数高度进行更高树间的高度比较

class Solution
{
public:
    int getHeight(TreeNode *node)
    {
        if (node == NULL)
        {
            return 0;
        }
        int left = getHeight(node->left);
        if (left == -1)
            return -1;
        int right = getHeight(node->right);
        if (right == -1)
            return -1;
        return abs(left - right) > 1 ? -1 : max(left, right) + 1;
    }
    bool isBalanced(TreeNode *root)
    {
        return getHeight(root) == -1 ? false : true;
    }
};

257.二叉树的所有路径

题目

257. 二叉树的所有路径 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归~回溯
注意回溯，保证更换方向时能够正确记录路径

class Solution
{
private:
    void traversal(TreeNode *cur, vector<int> &path, vector<string> &result)
    {
        path.push_back(cur->val);
        if (cur->left == NULL && cur->right == NULL)
        {
            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)
        {
            traversal(cur->left, path, result);
            path.pop_back();
        }
        if (cur->right)
        {
            traversal(cur->right, path, result);
            path.pop_back();
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode *root)
    {
        vector<int> path;
        vector<string> result;
        if (root == NULL)
            return result;
        traversal(root, path, result);
        return result;
    }
};