0.引言

• 110.平衡二叉樹
• 257. 二叉樹的所有路徑
• 404.左葉子之和
• 513.找樹左下角的值

1.# 平衡二叉樹

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹*每個節(jié)點 *的左右兩個子樹的高度差的絕對值不超過 1 。

示例 1：

image.png

輸入：root = [3,9,20,null,null,15,7]
輸出：true

示例 2：

image.png

輸入：root = [1,2,2,3,3,null,null,4,4]
輸出：false

示例 3：

輸入：root = []
輸出：true

提示：

• 樹中的節(jié)點數(shù)在范圍 [0, 5000] 內(nèi)
• -10<sup>4</sup> <= Node.val <= 10<sup>4</sup>

Discussion | Solution

1.1.遞歸法

/*
 * @lc app=leetcode.cn id=110 lang=cpp
 *
 * [110] 平衡二叉樹
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    if (root == nullptr) return true;
    bool res = true;
    dfs(root, res);
    return res;
  }

 private:
  // 以觸底反彈的后續(xù)遍歷進(jìn)行，同時使用左右子樹的思想，使用引用保存結(jié)果
  int dfs(TreeNode* node, bool& res) {
    if (node== nullptr ) {
      return 0;
    }
    int left_depth = dfs(node->left, res);
    int right_depth = dfs(node->right, res);
    if (std::abs(right_depth - left_depth) > 1) res = false;
    return 1 + std::max(left_depth, right_depth);
  }
};
// @lc code=end

這個題用迭代法就不是很直觀了。

2. 二叉樹的所有路徑

給你一個二叉樹的根節(jié)點 root ，按 任意順序 ，返回所有從根節(jié)點到葉子節(jié)點的路徑。

葉子節(jié)點 是指沒有子節(jié)點的節(jié)點。

示例 1：

image.png

輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]

示例 2：

輸入：root = [1]
輸出：["1"]

提示：

• 樹中節(jié)點的數(shù)目在范圍 [1, 100] 內(nèi)
• -100 <= Node.val <= 100

Discussion | Solution

2.1.遞歸法

/*
 * @lc app=leetcode.cn id=257 lang=cpp
 *
 * [257] 二叉樹的所有路徑
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  vector<string> binaryTreePaths(TreeNode* root) {
    std::vector<std::string> res;
    dfs(root, "", res);
    return res;
  }

 private:
  // 很明顯是使用前序遍歷
  void dfs(TreeNode* node, std::string one_path,
           std::vector<std::string>& paths) {
    if (node->left == nullptr && node->right == nullptr) {
      one_path += std::to_string(node->val);
      paths.push_back(one_path);
      return;
    }
    // 隱式回溯
    if (node->left) dfs(node->left, one_path + std::to_string(node->val) + "->", paths);
    if (node->right) dfs(node->right, one_path + std::to_string(node->val) + "->", paths);
  }
};
// @lc code=end

3. 左葉子之和

給定二叉樹的根節(jié)點 root ，返回所有左葉子之和。

示例 1：

輸入: root = [3,9,20,null,null,15,7] 
輸出: 24 
解釋: 在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24

示例 2:

輸入: root = [1]
輸出: 0

提示:

• 節(jié)點數(shù)在 [1, 1000] 范圍內(nèi)
• -1000 <= Node.val <= 1000

Discussion | Solution

3.1.遞歸法

class Solution {
 public:
  int sumOfLeftLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    int sum = 0;
    dfs(root, false, sum);
    return sum;
  }

 private:
  // 前序遍歷
  void dfs(TreeNode* node, bool is_left_node, int& sum) {
    if (node->left == nullptr && node->right == nullptr) {
      if (is_left_node) {
        sum += node->val;
      }
      return;
    }
    if (node->left) dfs(node->left, true, sum);
    if (node->right) dfs(node->right, false, sum);
  }
};

4.找樹左下角的值

給定一個二叉樹的 根節(jié)點 root，請找出該二叉樹的 **最底層 最左邊 **節(jié)點的值。

假設(shè)二叉樹中至少有一個節(jié)點。

示例 1:

image.png

輸入: root = [2,1,3]
輸出: 1

示例 2:

image.png

輸入: [1,2,3,4,null,5,6,null,null,7]
輸出: 7

提示:

• 二叉樹的節(jié)點個數(shù)的范圍是 [1,10<sup>4</sup>]
• -2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1

Discussion | Solution

4.1.遞歸法

/*
 * @lc app=leetcode.cn id=513 lang=cpp
 *
 * [513] 找樹左下角的值
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  int findBottomLeftValue(TreeNode* root) {
    int depth = 0, res;
    dfs(root, false, 1, depth, res);
    return res;
  }

 private:
  // 前序遍歷
  void dfs(TreeNode* node, bool is_left_node, int cur_depth, int& depth,
           int& res) {
    if (node->left == nullptr && node->right == nullptr) {
      if (cur_depth > depth) {
        depth = cur_depth;
        res = node->val;
      }
      return;
    }
    if (node->left) dfs(node->left, true, cur_depth + 1, depth, res);
    if (node->right) dfs(node->right, false, cur_depth + 1, depth, res);
  }
};
// @lc code=end