本巨巨推荐DFS从binary tree开始写 并且要用递回的方式
用stack可以 但是全局视野比较没有解子问题的感觉
类似这一题
98. Validate Binary Search Tree
这题就是要你验证 这是不是一个Binary Search Tree
其实就是不断解以下这个子问题
1. 左子树是不是BST
如果不是 那此Binary Tree不是BST
2. 如果左子树是BST 那根节点的值是不是比左子树最大的还大
如果不是 那此Binary Tree也不是BST
3. 右子树是不是BST 并且里头所有的值都大于根节点的值
那我们来看一个例子
按照上面的逻辑
5
/ \
3 7
/ \ /
1 4 6
1. 左子树是不是BST 那我们就要看 3
/ \
1 4
喔喔 还有左子树 再来看 那 1 是不是BST? 是
那同时用一个变量来存1的值 prev = 1
那再来就是
2. 如果左子树是BST 那根节点的值是不是比左子树最大的还大
3 是不是比1大 是 并且更新prev = 3
再来
3. 右子树是不是BST 并且里头所有的值都大于根节点的值
4 是不是 BST? 是 那4是不是比3大? 是
再来更新prev = 4
我们解完 3
/ \
1 4
再来就要看 5
\
7
/
6
解完 5的左子树了 那就回到
2.如果左子树是BST 那根节点的值是不是比左子树最大的还大
刚刚的prev = 4 那5有没有比4大? 有 更新prev=5
再来就是
3. 右子树是不是BST 并且里头所有的值都大于根节点的值
又是一个子问题
我们要来看 7 的 1. 左子树是BST
/
6
6是不是BST? 是 有没有大于5? 有 更新prev=6
2. 如果左子树是BST 那根节点的值是不是比左子树最大的还大
7有没有比6大? 有 更新prev=7
过完整棵树 发现所有问题的1. 2. 3. 都是true 那我们就可以说这个二元树是一颗BST
本巨巨觉得DFS的精神就是要你站在子问题的视野来解题 忘掉你从哪里来
然后从子子子子子子子问题开始解回去
用stack结构来解这题也行 也是DFS 也比较理想
变成一个用stack做inorder traversal
不会让你stack overflow 也比较快 不用caller callee一直跳
但就少了解子问题的味道 我觉得拉
※ 引述《cosmite (焼き団子)》之铭言：
: 最近开始Leetcode
: 发现字串处理和系统设计的的题目较DFS容易写
: DFS的题目看解答看得懂
: 但是要自己从无到有写一次
: 包括边界条件和递回判断式怎么写 却写不出来
: （中等难度）
: 到底是哪里出问题？
: 我是不是题目写太少了
: 应该从最简单的DFS题目 反复不同写
: 写到建函示变反射动作吗？
: 有没有人能救我==
: 卦
: