分类 默认分类 下的文章

Binary Tree Inorder Traversal 解法

原题:点击这里
题目大意:返回二叉树的中序遍历序列。
题目思路:有了上次在Recover Binary Search Tree里面的Morris遍历算法,加上所熟知的递归和非递归解法,二叉树的遍历算法已经有三种了,借此机会也总结一下。

阅读全文

Unique Binary Search Tree - ii 解法

原题:点击这里
题目大意:给定n个节点数目,返回所有的储存1, 2..., n的二叉搜索树。
题目思路:之前的Unique Binary Tree是要求返回树的数目,就是数论当中的卡塔兰数的概念,而这个题目难度要稍微大一些,要求返回所有的二叉搜索树,问题就来了。题目最后要求返回的是vector,肯定是记录了所有的根节点的vector容器,其实我在这里困扰了很久,不知道最后返回的结果里面存的是什么。第二就是如何遍历所有的情况。

阅读全文

Interleaving String 解法

原题:点击这里
题目大意:判断给定的一个字符串s3能够由s1和s2交织得到。
题目思路:刚看到这个题目就想起来跟之前做过的Distinct Subsequences意思差不多,只不过那个是由于一个字符串求顺序子串的问题,这个题目是两个字符串顺序交织得到,一分一合,所以思路应该是类似的,不过那道题目需要求顺序子串的数目,因此难度可能稍微大一些。

阅读全文

Validate Binary Search Tree 解法

原题:点击这里
题目大意:验证二叉树是否是二叉搜索树。
题目思路:有了Recover Binary Search Tree的经验之后,最直接的办法就是利用BST的中序遍历是递增序列的特点,进行判断。有三种大致差不多的思路。

阅读全文

Recover Binary Search Tree 解法

原题:点击这里
题目大意:二叉搜索树的两个节点被错误的交换了位置,请将其恢复成原来的结构。
题目思路:我刚开始的思路是希望能找到这两个节点,然后交换回来,分为两种类型:
(1)子节点与子节点交换;
(2)子节点与父节点交换。
按照这个思路,想了好久,递归的方法肯定是不行的,因为BST的规则是左子树所有的节点必须父节点,右子树所有的节点必须大于父节点,而且如何识别这两个节点就是个很大的问题。

阅读全文