网站建设报价清单,手机建站程序免费下载,济南网站优化多少钱,软文范文200字110. 平衡二叉树
简单 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。 本题中#xff0c;一棵高度平衡二叉树定义为#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1#xff1a; [图片] 输入#xff1a;root [3,9,20,null…110. 平衡二叉树
简单 给定一个二叉树判断它是否是高度平衡的二叉树。 本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 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] 内-10(4) Node.val 10(4)
思考
递归数值传递问题
代码
func isBalanced(root *TreeNode) bool {if root nil {return true}_, flag : dfs_isBalanced(root)return flag
}func dfs_isBalanced(root *TreeNode) (int, bool) {if root nil {return 0, true}// 获取左右子树的高度和平衡信息l, l_flag : dfs_isBalanced(root.Left)r, r_flag : dfs_isBalanced(root.Right)// 检查当前子树是否平衡if !l_flag || !r_flag || abs(l-r) 1 {return max(l, r) 1, false}// 返回当前子树的高度return max(l, r) 1, true
}func abs(x int) int {if x 0 {return -x}return x
}func max(a, b int) int {if a b {return a}return b
}257. 二叉树的所有路径
简单 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。
示例 1 [图片] 输入root [1,2,3,null,5] 输出[“1-2-5”,“1-3”] 示例 2 输入root [1] 输出[“1”]
提示
树中节点的数目在范围 [1, 100] 内-100 Node.val 100
代码
func binaryTreePaths(root *TreeNode) []string {res : make([]string, 0)temp : make([]int, 0)binaryTreePaths_dfs(root, temp, res)return res
}func binaryTreePaths_dfs(root *TreeNode, s []int, res *[]string) {if root nil {return}s append(s, root.Val)if root.Left nil root.Right nil {// 只有在叶子节点时将路径添加到结果path : strings.Trim(strings.Join(strings.Fields(fmt.Sprint(s)), -), )path strings.Trim(path, [)path strings.Trim(path, ])*res append(*res, path)}binaryTreePaths_dfs(root.Left, s, res)binaryTreePaths_dfs(root.Right, s, res)
}
var res []string //不安全学习上面的方法func binaryTreePaths(root *TreeNode) []string {resmake([]string,0)tmp : dfs_BTP(root, tmp)return res
}func dfs_BTP(root *TreeNode, tmp string) {if root nil {return}if len(tmp)0{tmp tmp strconv.Itoa(root.Val)}else{tmp tmp - strconv.Itoa(root.Val)}if root.Left nil root.Right nil {res append(res, tmp)}dfs_BTP(root.Left, tmp)dfs_BTP(root.Right, tmp)return
}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
代码
func sumOfLeftLeaves(root *TreeNode) int {if root nil {return 0}//左子树left : sumOfLeftLeaves(root.Left) //没有左子树就是左叶子节点if root.Left ! nil root.Left.Left nil root.Left.Right nil {left root.Left.Val}//右子树的左叶子节点right : sumOfLeftLeaves(root.Right)return left right
}
