palidin 发布的文章

平衡二叉树


给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: > 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] ``` 3 / \ 9 20 / \ 15 7 ``` 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] ``` 1 / \ 2 2 / \ 3 3 / \ 4 4 ``` 返回 false 。 ``` bool isBalanced(TreeNode* root) { if (root == NULL) return true; int x = depth(root->left) - depth(root->right); if (x>1 || x<-1) return false; else return isBalanced(root->left) && isBalanced(root->right); } int depth(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return max(depth(root->left), depth(root->right)) + 1; } ```

最大二叉树


给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下: 二叉树的根是数组中的最大元素。 - 左子树是通过数组中最大值左边部分构造出的最大二叉树。 - 右子树是通过数组中最大值右边部分构造出的最大二叉树。 - 通过给定的数组构建最大二叉树,并且输出这个树的根节点。 ``` 输入: [3,2,1,6,0,5] 输入: 返回下面这棵树的根节点: 6 / \ 3 5 \ / 2 0 \ 1 ``` 递归实现: ``` TreeNode* constructMaximumBinaryTree(vector& nums) { if (nums.empty()) { return NULL; } auto iter = max_element(nums.begin(), nums.end()); vector left, right; for (auto i = nums.begin(); i != nums.end(); i++) { if (i < iter) { left.push_back(*i); } if (i > iter) { right.push_back(*i); } } TreeNode* root = new TreeNode(*iter); root->left = constructMaximumBinaryTree(left); root->right = constructMaximumBinaryTree(right); return root; } ```

二叉树的层次遍历


给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7], ``` 3 / \ 9 20 / \ 15 7 ``` 返回其层次遍历结果: ``` [ [3], [9,20], [15,7] ] ``` 递归实现: ``` vector> levelOrder(TreeNode* root) { vector> collection; levelOrderRecur(root, &collection, 0); return collection; } void levelOrderRecur(TreeNode* root, vector>* collection, int deepth) { if (!root) { return; } if (collection->size() < deepth + 1) { collection->resize(deepth + 1); } collection->at(deepth).push_back(root->val); levelOrderRecur(root->left, collection, deepth + 1); levelOrderRecur(root->right, collection, deepth + 1); } ```

二叉树的后序遍历


给定一个二叉树,返回它的 *后序* 遍历。 ``` 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] ``` 递归实现: ``` vector postorderTraversal(TreeNode* root) { vector chain = {}; postorderTraversalRecur(root, &chain); return chain; } void postorderTraversalRecur(TreeNode* root, vector* chain) { if (!root) { return; } postorderTraversalRecur(root->left, chain); postorderTraversalRecur(root->right, chain); chain->push_back(root->val); } ```

二叉树的中序遍历


给定一个二叉树,返回它的 *中序* 遍历。 ``` 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] ``` 递归实现: ``` vector inorderTraversal(TreeNode* root) { vector chain = {}; inorderTraversalRecur(root, &chain); return chain; } void inorderTraversalRecur(TreeNode* root, vector* chain) { if (!root) { return; } inorderTraversalRecur(root->left, chain); chain->push_back(root->val); inorderTraversalRecur(root->right, chain); } ```