本文主要是介绍PreOrder, InOrder, PostOrder 题型总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最基本的 Preorder, Inorder, Postorder Traverse
Binary Tree Preorder traverse (用stack模拟,先进去right ,再进去left)
Binary Tree Inorder traverse (用stack模拟,每次push整个左枝的所有node,再变换到右边);
Binary Tree Postorder traverse (用stack模拟,跟preorder一样,只是左右的顺序不一样,最后我们可以反过来记录,这样就把原来的问题转换成了一个我熟知的类似于preoder traverse的问题, 记住linkedlist需要addFirst,才能每次O(1)加到前面;)
Kth Smallest Element in a BST (就是inorder的翻版,记录一下count = k就可以了);
Inorder Successor in BST ( Time Complexity: O(logK). 先遍历找到P,同时记录一下左拐的点, 然后如果有右儿子,就扎到最右边的最左下的node,如果没有右儿子,就是找到这个点最后一个左拐的点)
Inorder Successor in BST II (如果有右边节点,那么往右走,右边的最左边node就是答案。如果没有右边的node,那么向上找到第一个左拐的node,就是答案)
Validate Binary Search Tree (用stack来模拟inorder,然后记录pre node,如果pre node >= curnode return false; ) 这里注意的是stack 模拟为什么好?就是dfs是用的call stack,很容易stackoverflow,如果是用stack的话,那么就是利用heap来做 simulation,那样就很大,不会爆栈);
Construct Binary Tree from Preorder and Inorder Traversal (用preorder的root,去找inorder的root,确定leftsize大小,递归即可)
Construct Binary Tree from Inorder and Postorder Traversal (用postorder的最后一个root 去inorder里面找root,确定leftsize, 递归)
Construct Binary Search Tree from Preorder Traversal (用queue的思想,current, left, rig
这篇关于PreOrder, InOrder, PostOrder 题型总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!