MENU

二叉树的下一个结点&二叉树的上一个结点

August 8, 2018 • Read: 217 • 算法

二叉树的下一个结点

给定一棵二叉树和其中一个结点,如何找出中序遍历的下一个结点,树中的结点除了有两个分别指向左右子结点的指针外,还有一个指向父节点的指针

题解

最笨的方法就是一直网上回溯,直到找到了头结点,然后从头结点开始重新中序遍历一次树,然后得到答案

还有一种比较巧妙的方法,先判断当前结点有没有右子树,如果有,直接打印右子树中最左的结点即为答案;如果没有,就往上回溯,假设当前结点是x,父节点是p,如果x是p的左孩子,p就是答案,如果不是,就一直向上回溯x = p;p = p.parent;

二叉树的上一个结点

给定一棵二叉树和其中一个结点,如何找出中序遍历的上一个结点,树中的结点除了有两个分别指向左右子结点的指针外,还有一个指向父结点的指针

题解

这个的做法正好与上面相反,先判断当前结点x是否有左子树,如果有,打印左子树最右的结点;如果没有,还是网上回溯,如果x是p的右孩子,p就是答案

最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code