批量构建二叉查找树时的一个常见错误
2018-04-03
给定一个正整数 n，生成结点值为 1 ~ n 的所有二叉查找树： https://leetcode.com/problems/unique-binary-search-trees-ii/ Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique BST’s shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 这个问题可以用递归来求解，对于一个值，先分别生成它的左右子树的集合，然后把这些子树组合即可。 算法明明已经 AC 了，然而我在本地测试运行时却出现了 Exception: EXC_BAD_ACCESS (code=EXC_I386_GPFLT) 错误，这个错误是在访问已经 free 掉的内存时产生的。 经过一番 debug，终于发现了问题所在，同时发现网上很多方法也有这个 bug。 …
二叉树非递归遍历算法的快速实现
2018-03-25
二叉树的递归遍历简洁明了，而非递归遍历则相对复杂，三种递归思路有很大区别，还容易忘。如果不用线索二叉树的话，一般要用栈来实现，即便都是用栈实现，实现思路也有差别，这给我们理解和记忆带来困扰。 本文介绍利用栈来实现的二叉树非递归算法，主要目的是快速实现，而不是详细解释。 …