肉眼观察题。
设 \(f_{i,j,k}\) 表示区间 \([i,j]\) 的根为 \(k\) 时能否还原。这样枚举一个根 \(k\)，分别枚举两个儿子在两个区间的位置转移就好了，由于两个儿子是独立的，所以复杂度 \(\Theta(n^4)\)，无法通过。
考虑二叉搜索树的性质，区间 \([i,j]\) 组成的二叉搜索树的根一定是 \((i-1)\) 或 \((j+1)\)。要不然有一段放不上去。
既然根的父亲只有两种方式，状态的设计就可以大大的简化了。
我们设 \(f_{i,j,0}\) 表示区间 \([i,j)\) 组成的二叉搜索树的根的父亲是 \(j\) 能否还原，\(f_{i,j,1}\) 表示区间 \((i,j]\) 组成的二叉搜索树的根的父亲是 \(i\) 能否还原。
转移采用刷表法，用 \(f_{i,j,0/1}\) 来更新区间 \(f_{i-1,j,0/1}\) 和 \(f_{i,j+1,0/1}\) 即可。
代码。
标签：Recovering,BST,题解,二叉,搜索,区间 From： https://www.cnblogs.com/UperFicial/p/16659415.html