自己如何建设个网站首页,设计大赛官网,网站页面设计内容,网络设计培训班算法套路八——二叉树深度优先遍历#xff08;前、中、后序遍历#xff09;
算法示例#xff1a;LeetCode98#xff1a;验证二叉搜索树 给你一个二叉树的根节点 root #xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下#xff1a; 节点的左子树只…算法套路八——二叉树深度优先遍历前、中、后序遍历
算法示例LeetCode98验证二叉搜索树 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 方法一前序遍历——先判断再递归
前序遍历即先遍历根节点再遍历左右子树 前序遍历我们的思路是先判断当前结点是否满足二叉搜索树的条件再递归左右子树。 且如上图所示在二叉搜索树中使用前序遍历时有如上的规律从根节点传递取值范围对于任意一个结点其取值范围已经确定若结点值不在范围内则不是二叉搜索树。 步骤如下所示
root结点的取值范围为(-infinf)判断是否满足条件判断左子树是否是二叉搜索树且此时最大值应该小于root.val所以取值范围为-infroot.val]判断右子树是否是二叉搜索树且此时最小值应该大于root.val所以取值范围为[root.val,inf)对于2,3采取递归遍历
且注意判断root是否为空
class Solution:def isValidBST(self, root: Optional[TreeNode], left-inf, rightinf) - bool:if root is None:return Truex root.valreturn left x right and \self.isValidBST(root.left, left, x) and \self.isValidBST(root.right, x, right)方法二中序遍历——先判断再递归
中序遍历即先遍历左节点、根节点最后遍历右节点 且中序遍历下二叉搜索树应该为递增数组所以我们直接判断当前节点值是否大于上一个遍历的节点值pre 其实这也等价于约束节点的范围在中序遍历时只需要修改最小值即取值范围是(pre,inf)
判断左子树是否是二叉搜索树且记录左子树最后一个被遍历的节点值为pre也是左子树的最大值比较当前节点指是否大于pre即取值范围是(pre,inf)判断右子树是否是二叉搜索树对于1,3采取递归遍历
class Solution:pre -infdef isValidBST(self, root: Optional[TreeNode]) - bool:if root is None:return Trueif not self.isValidBST(root.left):return Falseif root.valself.pre:return Falseself.pre root.valreturn self.isValidBST(root.right)
方法三后序遍历——先递归在判断
后序遍历即先遍历左节点、右节点最后遍历根节点 后序遍历也可以传递节点的范围不过是从叶子节点向根节点传递根节点需要大于左子树的最大值小于右子树的最小值。
如果当今节点为null空节点则返回(inf,-inf)因为任何值都会小于inf任何值都会大于-inf这样就不会影响到树的最大最小值的取值可以仔细体会。遍历左子树且返回左子树的最小值l_min与最大值l_max遍历右子树且返回右子树的最小值r_min与最大值r_max比较当前节点的值若取值位于l_max ,r_min)则更新最小值与最大值并返回即min(l_min, x), max(r_max, x)。若取值不在范围内则表示不是二叉搜索树此时我们返回正常情况不会返回的-infinf来表示False比较返回值是否是正常值这等价与判断是否等于inf无穷即非正常值若等于inf则返回False若不等于inf则返回True
class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:def dfs(node: Optional[TreeNode]) - Tuple:if node is None:return inf, -infl_min, l_max dfs(node.left)r_min, r_max dfs(node.right)x node.val# 也可以在递归完左子树之后立刻判断如果不是二叉搜索树就不用递归右子树了if x l_max or x r_min:return -inf, inf#返回无穷表示为False不满足搜索树return min(l_min, x), max(r_max, x)return dfs(root)[1] ! inf总结
前序遍历在某些数据下不需要递归到边界base case就能返回而另外两种需要递归到至少一个边界从这个角度上来说它是最快的。 中序遍历很好地利用到了二叉搜索树的性质使用到的变量最少。 后序遍历的思想是最通用的即自底向上计算子问题的过程。想要学好动态规划的话请务必掌握这个思想。 且由以上示例代码都可以看出在代码书写时要定义内部匿名函数dfs不然可能会由于LeetCode判断问题影响结果
算法练习一LeetCode230. 二叉搜索树中第K小的元素 给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数。 利用特性中序遍历下二叉搜索树应该为递增数组 本题可以采用中序遍历每次遍历时k–当k为0时则表示当前结点为第k个结点则令ans等于该值
func kthSmallest(root *TreeNode, k int) int {var ans intvar dfs func(node *TreeNode) dfsfunc(node *TreeNode) {if nodenil{return }dfs(node.Left)k--if k0{ansnode.Val}dfs(node.Right)}dfs(root)return ans
}算法练习二LeetCode501. 二叉搜索树中的众数 给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。如果树中有不止一个众数可以按 任意顺序 返回。 利用特性中序遍历下二叉搜索树应该为递增数组 本题可以采用中序遍历将遍历节点与前一个节点比较然后使用变量curmax来记录当前节点与最多节点且注意要定义匿名函数解决。
func findMode(root *TreeNode) []int {var (ans []intpre, cur, max intdfs func(*TreeNode))dfs func(node *TreeNode) {if node nil {return}dfs(node.Left)if node.Val pre {cur} else {cur 1}if cur max {max curans []int{node.Val}} else if cur max {ans append(ans, node.Val)}pre node.Valdfs(node.Right)}dfs(root)return ans
}算法练习三LeetCode530. 二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点 root 返回 树中任意两不同节点值之间的最小差值 。差值是一个正数其数值等于两值之差的绝对值。 利用特性中序遍历下二叉搜索树应该为递增数组 本题可以采用中序遍历将遍历节点与前一个节点比较然后使用变量premin来记录前一个结点节点值与当前最小差值并定义匿名函数解决。
func getMinimumDifference(root *TreeNode) int {min, pre : math.MaxInt64, -1var dfs func(node *TreeNode)dfsfunc(node *TreeNode){if nodenil{return }dfs(node.Left)sub:node.Val-preif subminpre!-1{minsub}prenode.Valdfs(node.Right)
}dfs(root)return min
}算法练习四LeetCode700. 二叉搜索树中的搜索 给定二叉搜索树BST的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null。 若 root 为空则返回空节点 若 valroot.val则返回 \textit{root}root 若valroot.val递归左子树 若 valroot.val递归右子树。
func searchBST(root *TreeNode, val int) *TreeNode {if root nil {return nil}if val root.Val {return root}if val root.Val {return searchBST(root.Left, val)}return searchBST(root.Right, val)
}算法进阶一LeetCode236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 本题可以使用分类讨论如下图所示定义函数dfs()返回当前结点node的子树是否找到p或q有以下情况
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {return dfs(root,p,q)
}
func dfs(node, p, q *TreeNode) *TreeNode{if node nil || node p || node q {return node}left : dfs(node.Left, p, q)right : dfs(node.Right, p, q)if left ! nil right ! nil {return node}if left ! nil {return left}return right
}算法进阶二LeetCode236. 二叉树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 本题与上题一样只不过在判断pq的位置时可以利用线索二叉树值的大小性质来判断
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {return dfs(root,p,q)
}
func dfs(node, p, q *TreeNode) *TreeNode{if node nil || node p || node q {return node}if node.Valp.Valnode.Valq.Val{return dfs(node.Left,p,q)}else if node.Valp.Valnode.Valq.Val{return dfs(node.Right,p,q)}return node
}
