做视频网站用什么云盘好,微信 存储wordpress,携程旅行网站建设分析,广告设计公司营业执照文章目录 110. 平衡二叉树解题思路源码 257. 二叉树的所有路径解题思路源码 404.左叶子之和解题思路源码 110. 平衡二叉树
给定一个二叉树#xff0c;判断它是否是平衡二叉树
示例 1#xff1a;
输入#xff1a;root [3,9,20,null,null,15,7]输出#xff1a;true
示例… 文章目录 110. 平衡二叉树解题思路源码 257. 二叉树的所有路径解题思路源码 404.左叶子之和解题思路源码 110. 平衡二叉树
给定一个二叉树判断它是否是平衡二叉树
示例 1
输入root [3,9,20,null,null,15,7]输出true
示例 2
输入root [1,2,2,3,3,null,null,4,4]输出false
示例 3
输入root []输出true
提示
树中的节点数在范围 [0, 5000] 内-104 Node.val 104
解题思路
求左右子树高度差小于等于1就是平衡二叉树跟之前的求深度差不多
源码
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}private int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);if (leftHeight -1) {return -1;}int rightHeight getHeight(root.right);if (rightHeight -1) {return -1;}// 左右子树高度差大于1return -1表示已经不是平衡树了if (Math.abs(leftHeight - rightHeight) 1) {return -1;}return Math.max(leftHeight, rightHeight) 1;}
} 257. 二叉树的所有路径
给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1
输入root [1,2,3,null,5]输出[“1-2-5”,“1-3”]
示例 2
输入root [1]输出[“1”]
提示
树中节点的数目在范围 [1, 100] 内-100 Node.val 100
解题思路
递归和回溯结合用前序遍历方便记录父节点到子节点的路径
源码
class Solution {ListString result new ArrayList();public ListString binaryTreePaths(TreeNode root) {deal(root, );return result;}public void deal(TreeNode node, String s) {if (node null)return;if (node.left null node.right null) {result.add(new StringBuilder(s).append(node.val).toString());return;}String tmp new StringBuilder(s).append(node.val).append(-).toString();deal(node.left, tmp);deal(node.right, tmp);}
}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
解题思路
左叶子节点节点A的左孩子不为空且左孩子的左右孩子都为空说明是叶子节点那么A节点的左孩子为左叶子节点 后序遍历方便获得递归回来的子树上左叶子的值也可以用迭代做。 这个题不适合用层序遍历因为一个节点是不是左叶子不能根据它来判断而是要通过它的父节点来判断所以要用后序
源码
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root null) return 0;int leftValue sumOfLeftLeaves(root.left); // 左int rightValue sumOfLeftLeaves(root.right); // 右int midValue 0;if (root.left ! null root.left.left null root.left.right null) { midValue root.left.val;}int sum midValue leftValue rightValue; // 中return sum;}
}
