题解
思路：找到最后一个叶子节点满足插入条件即可
代码
type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func insertIntoBST(root *TreeNode, val int) *TreeNode { if root == nil { root = &TreeNode{Val: val} return root } if root.Val > val { root.Left = insertIntoBST(root.Left, val) } else { root.Right = insertIntoBST(root.Right, val) } return root }
坑点
先看wa的代码
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func insertIntoBST(root *TreeNode, val int) *TreeNode { insert(root, val) return root } func insert(root *TreeNode, val int)*TreeNode { if root == nil { root = &TreeNode{ Val: val, Left: nil, Right: nil, } return root } if root.Val > val { root.Left=insert(root.Left, val) } else { root.Right=insert(root.Right, val) } return root }
分析
为什么传进去一个nil，我函数里不是创建了新的节点了吗？不是指针传递吗？思考一下，其实指针传递传递的是指针里面存的地址，只是把“nil”传给了“形参指针”，让形参指针存nil而已，形参指针和局部指针不是同一个，他们执行的地址是同一个。那么形参指针指向的地址变化了，和局部指针又有什么关系呢，局部指针依旧指向nil
