Home

Morris遍历二叉树

Morris遍历不使用栈,O(1)空间进行二叉树的遍历。 原理就是: 利用叶子结点的右空指针,临时性的指向中序遍历的后继结点。 与这篇文章的想法类似,前序和中序非常相近,顺序是相同的,不同的是访问的时机。 1. 前序、中序遍历 #pseudo code while 结点存在: if 左子树存在: 找到左子树的最右结点, 如果发现左子树的最右结点:#这个最右结点也就是当前结点在中序遍历下的前驱结点 该结点右指针指向当前结点 否则如果最右结点的右指针已经指向当前结点: 还原最右结点的右指针指向NULL else: 访问该结点 转到右...

Read more

由两种遍历结果构造二叉树

还是二叉树遍历的题目,不过是由遍历结果反推二叉树。 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 两个题目是类似的,关于树的问题第一反映就是递归。以中序、后序推导为例, 中序结果为LNR,后序结果为LRN,因此可以通过后序结果的最后一个node(即根节点),在中序结果中查找,就可以区分L,R,然后继续递归计算即可。 举个列子,假设二叉树为 1 / \ 2 3 / \ 4 5 中序遍历为 4 2 5 1 3 后序遍历为 ...

Read more