题目：513. 找树左下角的值
思路：
层序遍历是最好的选择了，先放右节点，再放左节点最后一个元素就是最左侧的节点。
说白了层序遍历就是广度优先搜索BFS。
代码：
func findBottomLeftValue(root *TreeNode) int {
node := root
q := []*TreeNode{root}
for len(q) > 0 {
node, q = q[0], q[1:]
if node.Right != nil {
q = append(q, node.Right) // 先放右节点
}
if node.Left != nil {
q = append(q, node.Left) // 再放左节点
}
}
return node.Val // 最后一个节点就是最左侧的节点
}
参考：
题目：112. 路径总和
思路：
当它是叶子节点的时候判断是不是相同，返回true 或者 false。
根节点是只要左右有一个true就是true。
代码1：
func calcHasPathSum(root *TreeNode,nowSum, targetSum int) bool {
if root.Left == nil && root.Right == nil {
if nowSum + root.Val == targetSum {
return true
}
return false
}
left, right := false, false
if root.Left != nil {
left = calcHasPathSum(root.Left, nowSum + root.Val, targetSum)
}
if root.Right != nil {
right = calcHasPathSum(root.Right, nowSum + root.Val, targetSum)
}
return left || right
}
代码2：
简化版
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, sum int) bool {
if root == nil {
return false
}
if root.Left == nil && root.Right == nil {
return sum-root.Val == 0
}
return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
参考：
题目：106. 从中序与后序遍历序列构造二叉树
思路：
- 第一步：如果数组大小为零的话，说明是空节点了。
- 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
- 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
- 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
- 第五步：切割后序数组，切成后序左数组和后序右数组
- 第六步：递归处理左区间和右区间
代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var (
hash map[int]int
)
func buildTree(inorder []int, postorder []int) *TreeNode {
hash = make(map[int]int)
for i, v := range inorder { // 用map保存中序序列的数值对应位置
hash[v] = i
}
// 以左闭右闭的原则进行切分
root := rebuild(inorder, postorder, len(postorder)-1, 0, len(inorder)-1)
return root
}
// rootIdx表示根节点在后序数组中的索引，l, r 表示在中序数组中的前后切分点
func rebuild(inorder []int, postorder []int, rootIdx int, l, r int) *TreeNode {
if l > r { // 说明没有元素，返回空树
return nil
}
if l == r { // 只剩唯一一个元素，直接返回
return &TreeNode{Val : inorder[l]}
}
rootV := postorder[rootIdx] // 根据后序数组找到根节点的值
rootIn := hash[rootV] // 找到根节点在对应的中序数组中的位置
root := &TreeNode{Val : rootV} // 构造根节点
// 重建左节点和右节点
root.Left = rebuild(inorder, postorder, rootIdx-(r-rootIn)-1, l, rootIn-1)
root.Right = rebuild(inorder, postorder, rootIdx-1, rootIn+1, r)
return root
}