云海翻腾

分类

C++(5) 程序/算法设计(2) 题解(29)

/ 注册

全部文章（共2篇）

题解 | #二叉搜索树的后序遍历序列#

BST的特点是对任意结点，左子树小于该结点，右子树大于该结点。后序遍历产生的序列为左子树-右子树-结点。所以可知后序遍历序列的最后一个元素即为BST的根，再根据大小规律，可以找到左右子树对应的序列。递归处理这两个序列即可。找左右子树序列时可采用二分查找法，虽然左右子树序列不是完全有...

C++ 排序树二叉树递归

2021-10-16

0 421

题解 | #在二叉树中找到两个节点的最近公共祖先#

方法一通过深度优先遍历，分别找出从根到两个结点的路径，如1-2-3和1-2-5，那么路径的相同部分1-2的最后一个结点2即是最近祖先方法二递归考虑：如果当前结点为空，返回空；否则看当前结点是否为两个结点中的一个，只要是，那么当前结点一定是最近祖先，否则，递归左树：左树中没找到，递归右树...

C++ 二叉树递归深度优先搜索

2021-10-11

0 362