【Leetcode -404.左子叶之和 -543.二叉树的直径】

简介: 【Leetcode -404.左子叶之和 -543.二叉树的直径】

Leetcode -404.左子叶之和

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

示例 1:

输入: root = [3, 9, 20, null, null, 15, 7]

输出 : 24

解释 : 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例 2 :

输入 : root = [1]

输出 : 0

提示 :

节点数在 [1, 1000] 范围内

  • 1000 <= Node.val <= 1000

思路:化为子问题使用变量 ans 记录左子树和右子树的左子叶之和;结束条件为左子树为空、右子树为叶子或者空;

//判断是否是叶子
    bool isLeaves(struct TreeNode* root)
    {
        if (root->left == NULL && root->right == NULL)
            return true;
        return false;
    }
    int sumOfLeftLeaves(struct TreeNode* root)
    {
        //ans 记录左子叶之和
        int ans = 0;
        //根的左子树不为空,就判断它的左子树是否是叶子,是叶子就返回叶子的 val;否则继续递归其左子树
        if (root->left)
            ans += isLeaves(root->left) ? root->left->val : sumOfLeftLeaves(root->left);
        //递归完左子树递归右子树,寻找右子树的左子叶
        //根的右子树不为空,且不能是叶子
        if (root->right && !isLeaves(root->right))
            ans += sumOfLeftLeaves(root->right);
        return ans;
    }

Leetcode -543.二叉树的直径

题目:给你一棵二叉树的根节点,返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1:

输入:root = [1, 2, 3, 4, 5]

输出:3

解释:3 ,取路径[4, 2, 1, 3] 或[5, 2, 1, 3] 的长度。

示例 2:

输入:root = [1, 2]

输出:1

提示:

树中节点数目在范围[1, 104] 内

  • 100 <= Node.val <= 100

思路:题意为求最大左右子树长度之和;化为子问题用变量 max 比较左右子树的高度和与 max 的较大值,记录 max ,最后返回 max;

int max = 0;
    int MaxHeight(struct TreeNode* root)
    {
        if (root == NULL)
            return 0;
        //左右子树的高度
        int leftHeight = MaxHeight(root->left);
        int rightHeight = MaxHeight(root->right);
        //max 取 max 与 左右子树高度和的较大值 
        max = fmax(max, leftHeight + rightHeight);
        //返回高度
        return fmax(leftHeight + 1, rightHeight + 1);
    }
    int diameterOfBinaryTree(struct TreeNode* root)
    {
        //max 置0是因为在Leetcode中会多次调用diameterOfBinaryTree函数,所以每次调用都需要置0
        max = 0;
        MaxHeight(root);
        return max;
    }
目录
相关文章
|
28天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
18 2
|
28天前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
28天前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
13 2
|
28天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
15 0
|
28天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
13 0
|
28天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
12 0
|
28天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
28天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
13 0
|
3月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
3月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历