前言
持续更新了
正文
问题来源
本问题来自leetcode上的99题。
问题描述
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
分析：
func recoverTree(root *TreeNode) {
visit := make([]*TreeNode, 0)
index := make([]int, 0)
midOrder(root, &visit)
for i := 0; i < len(visit)-1; i++ {
if visit[i].Val > visit[i+1].Val {
if len(index) == 0 {
index = append(index, i)
} else {
index = append(index, i+1)
}
}
}
if len(index) == 1 {
i := index[0]
visit[i].Val, visit[i+1].Val = visit[i+1].Val, visit[i].Val
return
}
i := index[0]
j := index[1]
visit[i].Val, visit[j].Val = visit[j].Val, visit[i].Val
}
func midOrder(root *TreeNode, res *[]*TreeNode) {
if root == nil {
return
}
midOrder(root.Left, res)
*res = append(*res, root)
midOrder(root.Right, res)
}
总结：
勤思考。
结语
不管怎么样好好加油。
