day17 | 二叉树4

0.引言

• 110.平衡二叉树
• 257. 二叉树的所有路径
• 404.左叶子之和
• 513.找树左下角的值

1.# 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 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

提示：

• 树中的节点数在范围 [0, 5000] 内
• -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:
  // 以触底反弹的后续遍历进行，同时使用左右子树的思想，使用引用保存结果
  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. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

image.png

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

示例 2：

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

提示：

• 树中节点的数目在范围 [1, 100] 内
• -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. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

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

提示:

• 节点数在 [1, 1000] 范围内
• -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.找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 **最底层 最左边 **节点的值。

假设二叉树中至少有一个节点。

示例 1:

image.png

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

示例 2:

image.png

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

提示:

• 二叉树的节点个数的范围是 [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