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; }