亲宝软件园·资讯

展开

[leetcode] 树(Ⅰ)

sinkinben 人气:0
均为 Simple 难度的水题。 ## [二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/) 题目[94]:给定一个二叉树,返回它的*中序* 遍历。 解题思路:Too simple. ```cpp class Solution { public: vector inorderTraversal(TreeNode *root) { return inorderNonRec(root); vector v; innerTraversal(root, v); return v; } void innerTraversal(TreeNode *p, vector &v) { if (p == nullptr) return; innerTraversal(p->left, v); v.push_back(p->val); innerTraversal(p->right, v); } vector inorderNonRec(TreeNode *root) { vector v; if (root != nullptr) { stack s; auto p = root; while (!s.empty() || p != nullptr) { if (p != nullptr) { s.push(p); p = p->left; } else { p = s.top(), s.pop(); v.push_back(p->val); p = p->right; } } } return v; } }; ``` ## [相同的树](https://leetcode-cn.com/problems/same-tree/) 题目[100]:给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 ``` 输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true ``` 解题思路:递归。 ```cpp #include "leetcode.h" class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { return innerCheck(p, q); } bool innerCheck(TreeNode *p, TreeNode *q) { if ((p == nullptr) ^ (q == nullptr)) return false; if (p == nullptr && q == nullptr) return true; if (p->val != q->val) return false; return innerCheck(p->left, q->left) && innerCheck(p->right, q->right); } }; ``` ## [对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/) 题目[101]:给定一个二叉树,检查它是否是镜像对称的。 示例 ``` input: 1 / \ 2 2 / \ / \ 3 4 4 3 output: true ``` 解题思路:递归。 ```cpp class Solution { public: bool isSymmetric(TreeNode *root) { if (root == nullptr) return true; return innerCheck(root->left, root->right); } bool innerCheck(TreeNode *p, TreeNode *q) { if ((p == nullptr) ^ (q == nullptr)) return false; if (p == nullptr) return true; if (p->val != q->val) return false; return innerCheck(p->left, q->right) && innerCheck(p->right, q->left); } }; ``` ## [二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/) 题目[104]:给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 示例 ``` input: 3 / \ 9 20 / \ 15 7 output: 3 ``` 解题思路:DFS 。 ```CPP #define max(a, b) ((a) > (b) ? (a) : (b)) class Solution { public: int maxDepth(TreeNode *root) { return dfs(root); } int dfs(TreeNode *p) { if (p == nullptr) return 0; int a = dfs(p->left), b = dfs(p->right); return max(a, b) + 1; } }; ``` 值得注意的是,不能 `return max(dfs(p->lect), dfs(p->right)) + 1`,因为宏展开后就会执行 4 次 DFS 。 ## [二叉树的层次遍历 II](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/) 题目[107]:给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)。 示例 ``` Input: 3 / \ 9 20 / \ 15 7 Output: [[15,7], [9,20], [3]] ``` 解题思路:使用队列进行层次遍历,同时记下层数,使用 `map` 记录各个层次的节点。 ```cpp struct Tuple { TreeNode *ptr; int level; Tuple(TreeNode *q = nullptr, int l = -1) : ptr(q), level(l) {} }; class Solution { public: vector> levelOrderBottom(TreeNode *root) { if (root == nullptr) return vector>(); map> m; queue q; q.push(Tuple(root, 0)); while (!q.empty()) { Tuple p = q.front(); q.pop(); m[p.level].push_back(p.ptr->val); if (p.ptr->left) q.push(Tuple(p.ptr->left, p.level + 1)); if (p.ptr->right) q.push(Tuple(p.ptr->right, p.level + 1)); } vector> v; for (auto x : m) v.push_back(x.second); return vector>(v.rbegin(), v.rend()); } }; ``` ## [将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/) 题目[108]:将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1。 示例 ``` 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 ``` 解题思路:二叉搜索树的性质是**中序遍历呈升序**,所以数组的中间元素 `nums[mid]` 必然是二叉树的根节点。所以 `[start, mid - 1]` 是左子树,`[mid + 1, end]` 是右子树,递归处理。如果数组长度为偶数,中间元素有 2 个,可任意取一个为根节点。 ```cpp class Solution { public: TreeNode *sortedArrayToBST(vector &nums) { TreeNode *root = nullptr; innerCreate(nums, 0, nums.size() - 1, root); return root; } void innerCreate(vector &v, int start, int end, TreeNode *&p) { if (start > end) return; int mid = start + (end - start) / 2; p = new TreeNode(v[mid]); innerCreate(v, start, mid - 1, p->left); innerCreate(v, mid + 1, end, p->right); } }; ``` ## [平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/) 题目[110]:给定一个二叉树,判断它是否是高度平衡的二叉树。 示例 ``` Input: [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 Output: true ``` 解题思路: + 暴力解法 ```cpp #include class Solution { public: bool isBalanced(TreeNode *root) { return forceSolution(root); } // brute force solution bool forceSolution(TreeNode *p) { if (p == nullptr) return true; bool flag = abs(height(p->left) - height(p->right)) <= 1; return flag && forceSolution(p->left) && forceSolution(p->right); } int height(TreeNode *p) { if (p == nullptr) return 0; return max(height(p->left), height(p->right)) + 1; } }; ``` 请注意一点细节,`flag && forceSolution(p->left) && forceSolution(p->right)` 效率要比 ` forceSolution(p->left) && forceSolution(p->right) && flag` 高。 显然,暴力解法对求高度存在需要「冗余」的情况,比如,我们知道 `h(left) = height(p->left)`,那么 `h(p) = h(left) + 1`,但是暴力解法仍然用 `h(p) = height(p)` 。 + 自底向上的递归 返回值表示以 `p` 为根的子树是否平衡,`height` 记录以 `p` 为根的子树的高度。 ```cpp bool isBalanced(TreeNode *root) { int height = 0; return innerIsBalanced(root, height); } bool innerIsBalanced(TreeNode *p, int &height) { if (p == nullptr) { height = 0; return true; } int lh = 0, rh = 0; if (innerIsBalanced(p->left, lh) && innerIsBalanced(p->right, rh) && abs(lh - rh) <= 1) { height = max(lh, rh) + 1; return true; } return false; } ``` ## [二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/) 题目[111]:给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 示例 ``` Input: 3 / \ 9 20 / \ 15 7 Output: 2 ``` 解题思路:记录每个节点层数的层次遍历(实质上是 BFS)。第一个叶子节点的层数就是答案。 ```cpp class Solution { public: int minDepth(TreeNode *root) { return (root == nullptr) ? 0 : bfs(root); } int bfs(TreeNode *root) { typedef pair Node; queue q; q.push(Node(root, 1)); while (!q.empty()) { auto &node = q.front(); q.pop(); if (node.first->left == nullptr && node.first->right == nullptr) return node.second; if (node.first->left != nullptr) q.push(Node(node.first->left, node.second + 1)); if (node.first->right != nullptr) q.push(Node(node.first->right, node.second + 1)); } return -1; } }; ``` ## [路径总和](https://leetcode-cn.com/problems/path-sum/) 题目[112]:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 示例 ``` Input: sum = 22 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 Output: true, because sum(5->4->11->2) = 22 ``` 解题思路:回溯法。`current` 记录当前的**遍历路径**的和。 ```cpp class Solution { public: bool hasPathSum(TreeNode *root, int sum) { bool result = false; innerSum(root, sum, 0, result); return result; } void innerSum(TreeNode *p, int target, int current, bool &result) { if (p == nullptr) return; current += p->val; if (current == target && p->left == nullptr && p->right == nullptr) { result = true; return; } innerSum(p->left, target, current, result); if (!result) innerSum(p->right, target, current, result); } }; ``` ## [翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/) 题目[226]:翻转一棵二叉树。 示例 ``` Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1 ``` 解题思路:对每个节点执行 `swap(p->left, p->right)` 。`TreeNode* &p` 表示的是指针的引用。 ```cpp class Solution { public: TreeNode *invertTree(TreeNode *root) { if (root != nullptr) innerInvert(root->left, root->right); return root; } void innerInvert(TreeNode *&l, TreeNode *&r) { auto p = l; l = r; r = p; if (l != nullptr) innerInvert(l->left, l->right); if (r != nullptr) innerInvert(r->left, r->right); } }; ``` ## [二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/) 题目[235]:给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 示例 ``` 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 ``` 解题思路:利用二叉搜索树的性质,左子树 < 根 < 右子树。那么: + `p.val < root.val && q.val < root.val`:在左子树搜索。 + `p.val > root.val && q.val < root.val`:在右子树搜索。 + 其他情况:`root` 就是公共祖先。 递归解法 ```cpp TreeNode *lca(TreeNode *root, TreeNode *p, TreeNode *q) { if (p->val < root->val && q->val < root->val) return lca(root->left, p, q); else if (p->val > root->val && q->val > root->val) return lca(root->right, p, q); else return root; } ``` 非递归解法 ```cpp TreeNode *lca2(TreeNode *root, TreeNode *p, TreeNode *q) { auto node = root; while (node != nullptr) { if (p->val < node->val && q->val < node->val) node = node->left; else if (p->val > node->val && q->val > node->val) node = node->right; else break; } return node; } ``` ## [二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths/) 题目[257]:给定一个二叉树,返回所有从根节点到叶子节点的路径。 示例 ``` 输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 ``` 解题思路:显而易见的回溯法(实际上也是二叉树的遍历),如果找到叶子节点,说明是一个完整的路径。 ```cpp #include "leetcode.h" class Solution { public: vector result; vector binaryTreePaths(TreeNode *root) { if (root != nullptr) preorder(root, ""); return result; } void preorder(TreeNode *p, string s) { bool l = (p->left != nullptr); bool r = (p->right != nullptr); if (l || r) s += to_string(p->val) + "->"; else if (!l && !r) { s += to_string(p->val); result.push_back(s); return; } if (l) preorder(p->left, s); if (r) preorder(p->right, s); } }; ``` ## [左叶子之和](https://leetcode-cn.com/problems/sum-of-left-leaves/) 题目[404]:计算给定二叉树的所有左叶子之和。 示例 ``` 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24 ``` 解题思路:遍历过程使用一个 `flag` 来表示本次节点是否为左子树。如果既是左子树,又是叶子节点,就是要累加的节点。 ```cpp #include "leetcode.h" class Solution { public: int sum = 0; int sumOfLeftLeaves(TreeNode *root) { if (root != nullptr) preorder(root, false); return sum; } void preorder(TreeNode *root, bool isLeft) { bool l = (root->left != nullptr); bool r = (root->right != nullptr); if (isLeft && !l && !r) sum += root->val; if (l) preorder(root->left, true); if (r) preorder(root->right, false); } }; ``` ## ⭐ [路径总和 III](https://leetcode-cn.com/problems/path-sum-iii/) 题目[437]:给定一个二叉树,它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。 示例 ``` root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 返回 3。和等于 8 的路径有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 ``` 解题思路:将二叉树的每一个完整路径看作是一个数组 `nums`(假设第一个元素是 `nums[1]`),那么本题就是要找到 `sum(i, j) = sum` 的下标 i 和 j 。 为此,使用一个数组 `v` ,`v[0] = 0`,`v[i]` 表示 `sum(nums[1] ... nums[i])` ,即 `nums` 前 i 个元素的和。那么 `sum(nums[i] ... nums[j]) = v[j] - v[i - 1]` 。 使用先序遍历每一个从根到叶子的路径。 ```cpp class Solution { public: int result = 0; int pathSum(TreeNode *root, int sum) { if (root == nullptr) return 0; int d = depth(root); vector v(d + 1); preorder(1, v, root, sum); return result; } int depth(TreeNode *p) { if (p == nullptr) return 0; return max(depth(p->left), depth(p->right)) + 1; } void preorder(int idx, vector &v, TreeNode *p, const int sum) { if (p == nullptr) return; v[idx] = v[idx - 1] + p->val; for (int i = 0; i < idx; i++) { if (v[idx] - v[i] == sum) result++; } preorder(idx + 1, v, p->left, sum); preorder(idx + 1, v, p->right, sum); } }; ``` ## ⭐[二叉搜索树中的众数](https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/) 题目[501]:给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。 示例 ``` Input: 1 \ 2 / 2 Output: [2] ``` 解题思路:利用BST的性质,中序遍历为升序序列。`current` 记录当前数字 `number` 出现的次数,`last` 记录上一次找到的「候选众数」出现的次数。 ```cpp class Solution { public: vector v; int current = 0; int last = 0; int number = 0x80000000; vector findMode(TreeNode *root) { if (root != nullptr) inorder(root); return v; } void inorder(TreeNode *p) { if (p == nullptr) return; inorder(p->left); if (last == 0) last = 1; if (p->val != number) current = 0; number = p->val; current++; if (current == last) v.push_back(number); if (current > last) { last = current; v.clear(), v.push_back(number); } inorder(p->right); } }; ``` ## [二叉搜索树的最小绝对差](https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/) 题目[530]:给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例 ``` 输入: 1 \ 3 / 2 输出:1 解释:最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。 ``` 解题思路:BST中序遍历呈升序。 ```cpp #include "leetcode.h" class Solution { public: int result = 0x7ffffff; int pre = 0x7fffffff; int getMinimumDifference(TreeNode *root) { inorder(root); return result; } void inorder(TreeNode *p) { if (p == nullptr) return; inorder(p->left); result = min(result, abs(p->val - pre)); pre = p->val; inorder(p->right); } }; ``` ## [把二叉搜索树转换为累加树](https://leetcode-cn.com/problems/convert-bst-to-greater-tree/) 题目[538]:给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 示例 ``` 输入: 原始二叉搜索树: 5 / \ 2 13 输出: 转换为累加树: 18 / \ 20 13 ``` 解题思路:逆中序遍历 BST 。 ```cpp class Solution { public: int sum = 0; TreeNode *convertBST(TreeNode *root) { postorder(root); return root; } void postorder(TreeNode *p) { if (p == nullptr) return; postorder(p->right); sum += p->val; p->val = sum; postorder(p->left); } }; ``` ## ⭐[二叉树的直径](https://leetcode-cn.com/problemshttps://img.qb5200.com/download-x/diameter-of-binary-tree/) 题目[534]:给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 ``` Input: 1 / \ 2 3 / \ 4 5 Output: 3 ``` 解题思路:所谓直径,就是二叉树中任意路径上的节点数减一。 对于二叉树中的每个节点 `node`,以 `node` 为根的子树,其直径为 `depth(node.left) + depth(node.right)` 。 + 自顶向下的递归 ```cpp int result = 0; int diameterOfBinaryTree(TreeNode *root) { preorder(root); return result; } int depth(TreeNode *p) { return p == nullptr ? 0 : max(depth(p->left), depth(p->right)) + 1; } void preorder(TreeNode *p) { if (p == nullptr) return; result = max(result, depth(p->left) + depth(p->right)); preorder(p->left); preorder(p->right); } ``` + 自底向上的递归 显然,对每个节点都调用一次 `depth` 函数,有很多冗余的遍历。求出每个节点的高度,实际上只需要一次自底向上的遍历。因为 `depth(p) = max(depth(p.left), depth(p.right)) + 1` 。因此可使用后序遍历。 ```cpp int result = 0; int diameterOfBinaryTree(TreeNode *root) { int height = 0; bottom2top(root, height); return result; } void bottom2top(TreeNode *p, int &height) { if (p == nullptr) { height = 0; return; } int l = height, r = height; bottom2top(p->left, l); bottom2top(p->right, r); height = max(l, r) + 1; result = max(result, l + r); } ``` ## [二叉树的坡度](https://leetcode-cn.com/problems/binary-tree-tilt/) 题目[563]:给定一个二叉树,计算整个树的坡度。一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。整个树的坡度就是其所有节点的坡度之和。 示例 ``` 输入: 1 / \ 2 3 输出: 1 解释: 结点的坡度 2 : 0 结点的坡度 3 : 0 结点的坡度 1 : |2-3| = 1 树的坡度 : 0 + 0 + 1 = 1 ``` 解题思路:实际上要解决的问题是**怎么求出每个子树的和**。显然还是采取自底向上的后序遍历。 ```cpp class Solution { public: int tilt = 0; int findTilt(TreeNode *root) { int sum = 0; postorder(root, sum); return tilt; } void postorder(TreeNode *p, int &sum) { if (p == nullptr) { return; } int l = sum, r = sum; postorder(p->left, l); postorder(p->right, r); sum += p->val + l + r; tilt += abs(l - r); } }; ``` ## [另一个树的子树](https://leetcode-cn.com/problems/subtree-of-another-tree/) 题目[572]:给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。 解题思路:暴力解法。先实现 `isSame(s, t)` 判断 `s` 和 `t` 是否完全相等,再遍历 `s` 的每一个节点 `p` ,判断 `isSame(p, t)` 。 ```cpp class Solution { public: bool isSubtree(TreeNode *s, TreeNode *t) { if (s == nullptr) return t == nullptr; queue q; q.push(s); while (!q.empty()) { auto p = q.front(); q.pop(); if (isSame(p, t)) return true; if (p->left != nullptr) q.push(p->left); if (p->right != nullptr) q.push(p->right); } return false; } bool isSame(TreeNode *s, TreeNode *t) { if ((s == nullptr) ^ (t == nullptr)) return false; if (s == nullptr && t == nullptr) return true; return (s->val == t->val) && isSame(s->left, t->left) && isSame(s->right, t->right); } }; ```

加载全部内容

相关教程
猜你喜欢
用户评论