共 2 篇文章
这次要记录的是做leetbook：二叉树的经历，这是一本很小的book，所以决定用一晚上的时间做完。传送门 树的遍历 t1 二叉树的先序遍历 常规操作，简单题要做难，所以考虑用多种方法来写。 递归法 最常规的递归法，按照根->左->右的顺序来写就可以了。 ```cpp class Solution { public: void solve(TreeNode*root, vector& a) { if(root == NULL) return; a.push_back(root->val); solve(root->left, a); solve(root->right, a); } vector preorderTraversal(TreeNode* root) { vector ans; solve(root, ans); return ans; } }; ``` 迭代法 迭代法是用栈模拟递归的操作。因为栈具有先入后弹的特性，所以优先压右儿子进栈。 ```cpp class Solution …
传送门 二叉搜索树是一颗特殊的二叉树，它满足以下条件： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左右子树也都是二叉搜索树 显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。 但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左子树与右子树的高度差的绝对值小于等于1左右子树也都是平衡二叉搜索树 同时定义平衡因子为节点左子树与右子树深度之差。 那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), …