企业文化墙设计网站推荐,东莞广告公司排名,响应式网站建设价位,正能量网站1、 110.平衡二叉树
题目#xff1a; 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。 本题中#xff0c;一棵高度平衡二叉树定义为#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
思路#xff1a;
经典后序遍历#xff0c;感…1、 110.平衡二叉树
题目 给定一个二叉树判断它是否是高度平衡的二叉树。 本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
思路
经典后序遍历感觉所有的后序遍历的二叉树都一样了因为要返回高度所以新建一个dfsgo 没有abs函数
func isBalanced(root *TreeNode) bool {return hou(root) ! -1
}
func hou(node *TreeNode) int {if node nil {return 0}leftHigh : hou(node.Left)if leftHigh -1 {return -1}rightHigh : hou(node.Right)if rightHigh -1 {return -1}if leftHigh-rightHigh 1 || rightHigh-leftHigh 1 {return -1}return 1max(leftHigh, rightHigh)
}
func max(a,b int) int {if ab {return a}; return b}2、257. 二叉树的所有路径
题目 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。
思路
叶子节点特性就是判断条件就是左右为空条件判断注意 res 的声明与初始化
var res []string
func binaryTreePaths(root *TreeNode) []string {res []string{}path(root, )return res
}
func path(node *TreeNode, list string) {if node nil {return }list strconv.Itoa(node.Val)// 想清楚逻辑if node.Left nil node.Right nil {res append(res, list)} else {list -path(node.Left, list)path(node.Right, list)}
}3、404. 左叶子之和
题目 给定二叉树的根节点 root 返回所有左叶子之和。
思路
后序左右中重点就是判断规则规则就是左节点之后处理一下是否拿这个节点的值
func sumOfLeftLeaves(root *TreeNode) int {if root nil {return 0}if root.Left nil root.Right nil {return 0}// 叶子节点leftNumber : sumOfLeftLeaves(root.Left)if root.Left ! nil root.Left.Leftnil root.Left.Rightnil {leftNumber root.Left.Val}rightNumber : sumOfLeftLeaves(root.Right) // right就算是叶子节点也不需要返回值// 这个条件怎么搞return leftNumberrightNumber
}
