算法训练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;
      }
  };