LeetCode 热题 100 | 二叉树（二）

���录

1  543. 二叉树的直径

2  102. 二叉树的层序遍历

3  108. 将有序数组转换为二叉搜索树

菜鸟做题，语言是 C++

1  543. 二叉树的直径

这道题和  124. 二叉树中的最大路径和  太像了

题眼：二叉树的 直径 是指树中任意两个节点之间 最长路径的长度 。

简而言之，就是找出一条路径，且这条路径上的节点最多。

解题思路：

• 从下往上遍历二叉树
• 当前子树中的最长路径 = 1 + 左子树中的最长路径 + 右子树中的最长路径
• 向父节点自荐当前子树中的最长路径 = 1 + max(左子树中的最长路径，右子树中的最长路径)

  为什么必须从 “左子树中的最长路径” 和 “右子树中的最长路径” 中选一个？不能都要吗？当然不行。我们要的是一条笔直的路径，如果左右子树都带上，那不就分叉了吗。

  思路说明图：

  对于绿色节点，在它作为根节点的子树中，最长路径 = 1 + 左子树中的最长路径 + 右子树中的最长路径；绿色节点（左子节点）向蓝色节点（父节点）自荐，自荐的最长路径 = 1 + max(左子树中的最长路径，右子树中的最长路径)。对于蓝色节点，在它作为根节点的子树中，最长路径 = 1 + 左子树中的最长路径 + 右子树中的最长路径。以此类推。

  class Solution {public:    int ans = 1;    int helper(TreeNode * root) {        if (!root) return 0;        int ltree = helper(root->left);        int rtree = helper(root->right);        ans = max(ans, 1 + ltree + rtree);        return 1 + max(ltree, rtree);    }    int diameterOfBinaryTree(TreeNode* root) {        helper(root);        return ans - 1;    }};

  说明：我们算的其实是最多节点数，而路径长度是边的条数，因此需要减一：

  return ans - 1;

  2  102. 二叉树的层序遍历

  是循环，不是递归

  层序遍历：逐层地，从左到右访问所有节点。

  解题思路：

  • 出队：从左到右遍历当前层中的每个节点
  • 入队：将每个节点的左右子节点存入队列中
  • 出队：从左到右遍历左右子节点，即下一层中的每个节点

    具体代码：

    ① 循环条件：当队列中还有节点没有被遍历时，即队列长度不为 0 时。

    while (q.size()) {}

    ② 遍历某一层中的所有节点：

    int currentLevelSize = q.size();for (int i = 0; i    
    此时队列的大小等于当前层中的节点个数。
      
    ③ 存入每个节点的左右子节点，即下一层中的所有节点。
     
    if (node->left) q.push(node->left);if (node->right) q.push(node->right);
       
    只有节点不为空时才需要被访问。
      
    class Solution {public:    vector levelOrder(TreeNode* root) {        if (!root) return {};        vector ans;        queue q;        q.push(root);        while (q.size()) {            int currentLevelSize = q.size();            ans.push_back(vector ());            for (int i = 0; i val);                if (node->left) q.push(node->left);                if (node->right) q.push(node->right);            }        }        return ans;    }};
       
    3  108. 将有序数组转换为二叉搜索树
     
    与对 105. 从前序与中序遍历序列构造二叉树 的理解有一点点像
     
    可以理解成：将有序数组视为中序遍历的结果，并将其还原回二叉树。
     
    中序遍历的结果数组的特点：(左子树，根节点，右子树)
     
    题眼：高度平衡二叉树 是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。因此，我们每次都取数组区间的中间值为根节点，代码如下：
     
    int mid = (left + right) / 2;
     
    完整代码：
     
    class Solution {public:    TreeNode* helper(vector& nums, int left, int right) {        if (left > right) return nullptr;        int mid = (left + right) / 2;        TreeNode* root = new TreeNode(nums[mid]);        root->left = helper(nums, left, mid - 1);        root->right = helper(nums, mid + 1, right);        return root;    }    TreeNode* sortedArrayToBST(vector& nums) {        return helper(nums, 0, nums.size() - 1);    }};