友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Tree 树

0000 ds tree 00
0000 ds tree 03

树的遍历,如果用递归,代码写起来很简单。但是用遍历,又该如何做呢?

凡是用递归能解决的问题,都可以使用遍历来解决。用递归来求解问题,无非就是使用了方法栈来保存相关信息。同样,可以使用 Stack 来自己动手维护这些信息。例如:

0000 ds tree 02

搜索二叉树,一个隐含的性质是如果中序遍历,其值是单调递增的。所以,如果两个节点交换位置了,则第一个错误节点是比较大的节点(后面的跑前面了),第二个错误节点为较小的节点(后面的跑前面了)。如果是相邻节点交换,也是类似。

将一棵搜索二叉树按后序遍历生成一个数组。那么,数组最后一个元素就是根节点,同时,从后向前遍历,第一个小于根节点值的地方就是左右树的分界线。然后再递归解析。就可以重建这棵搜索二叉树了。

社区里有人宣称: 中序遍历团灭系列二叉搜索树问题。这点可以尝试一下:

  1. 94. Binary Tree Inorder Traversal 中序遍历二叉树

  2. 530. 二叉搜索树的最小绝对差 二叉搜索树的最小绝对差

  3. 230. Kth Smallest Element in a BST 二叉搜索树中第k小的元素

  4. 501. Find Mode in Binary Search Tree 二叉搜索树中的众数

  5. [0938-range-sum-of-bst] 二叉搜索树的范围和

  6. [0653-two-sum-iv-input-is-a-bst] 两数之和IV-输入BST

  7. 98. Validate Binary Search Tree 验证二叉搜索树

需要加强的内容

  1. 基于 Morris 遍历的前序和后序遍历练习

  2. 前中后根遍历的非递归实现

  3. 利用 Morris 求树的最小深度: 111. Minimum Depth of Binary Tree,尝试一下最大深度。

技巧或者隐藏知识点

  1. 非递归法后序遍历,可以用一个取巧的办法,套用一下前序遍历,前序遍历是根左右,后序遍历是左右根,我们只需要将前序遍历的结果反转一下,就是根左右。如果使用Java实现,可以在链表上做文章,将尾插改成头插也是一样的效果。

  2. 归并排序和二叉树后根遍历的递归顺序是一样的。

Morris 遍历

二叉搜索树相关的的一些题目,很可能就会利用中序遍历是升序序列的特性来处理一下问题。那么,在时间复杂度相同,但空间复杂度都特别优秀的 Morris 遍历就是一个很好的选择。

0000 ds tree 01

树形 DP 套路

树形 DP 套路使用前提:如果题目求解目标是 S 规则,则求解流程可以定成以每一个节点为头节点的子树在 S 规则下的每一个答案,并且最终答案一定在其中。

  1. 以某个节点 X 为头节点的子树中,分析答案有哪些可能性,并且这种分析是以 X 的左子树、X 的右子树和 X 整棵树的角度来考虑可能性的。

  2. 根据第一步的可能性分析,列出所有需要的信息。

  3. 合并第二步的信息,对左树和右树提出同样的要求,并写出信息结构。

  4. 设计递归函数,递归函数是处理以 X 为头节点的情况下的答案,包括设计递归的 base case,默认直接得到左树和右树的所有信息,以及把可能性整合,并且要返回第三步的信息结构这四个小步骤。

路径问题

问题分类

二叉树路径的问题大致可以分为两类:

  1. 自顶向下:顾名思义,就是从某一个节点(不一定是根节点),从上向下寻找路径,到某一个节点(不一定是叶节点)结束。而继续细分的话还可以分成一般路径与给定和的路径。

  2. 非自顶向下:就是从任意节点到任意节点的路径,不需要自顶向下。

解题模板

这类题通常用深度优先搜索(DFS)和广度优先搜索(BFS)解决,BFS较DFS繁琐,这里为了简洁只展现DFS代码 下面是我对两类题目的分析与模板

一、自顶而下:
// **一般路径**
vector<vector<int>>res;
void dfs(TreeNode*root,vector<int>path)
{
    if(!root) return;  //根节点为空直接返回
    path.push_back(root->val);  //作出选择
    if(!root->left && !root->right) //如果到叶节点
    {
        res.push_back(path);
        return;
    }
    dfs(root->left,path);  //继续递归
    dfs(root->right,path);
}

// **给定和的路径**
void dfs(TreeNode*root, int sum, vector<int> path)
{
    if (!root)
        return;
    sum -= root->val;
    path.push_back(root->val);
    if (!root->left && !root->right && sum == 0)
    {
        res.push_back(path);
        return;
    }
    dfs(root->left, sum, path);
    dfs(root->right, sum, path);
}

这类题型DFS注意点:

  1. 如果是找路径和等于给定 target 的路径的,那么可以不用新增一个临时变量 curSum 来判断当前路径和,只需要用给定和 target 减去节点值,最终结束条件判断 target==0 即可

  2. 是否要回溯:二叉树的问题大部分是不需要回溯的,原因如下:

    二叉树的递归部分:dfs(root→left),dfs(root→right)已经把可能的路径穷尽了, 因此到任意叶节点的路径只可能有一条,绝对不可能出现另外的路径也到这个满足条件的叶节点的;

    而对比二维数组(例如迷宫问题)的DFS,for循环向四个方向查找每次只能朝向一个方向,并没有穷尽路径, 因此某一个满足条件的点可能是有多条路径到该点的

    并且visited数组标记已经走过的路径是会受到另外路径是否访问的影响,这时候必须回溯

  3. 找到路径后是否要return:取决于题目是否要求找到叶节点满足条件的路径,如果必须到叶节点,那么就要return;但如果是到任意节点都可以,那么必不能return,因为这条路径下面还可能有更深的路径满足条件,还要在此基础上继续递归

  4. 是否要双重递归(即调用根节点的dfs函数后,继续调用根左右节点的pathsum函数):看题目要不要求从根节点开始的,还是从任意节点开始

二、非自顶而下:

这类题目一般解题思路如下:

设计一个辅助函数 maxPath,调用自身求出以一个节点为根节点的左侧最长路径 left 和右侧最长路径 right,那么经过该节点的最长路径就是 left+right

接着只需要从根节点开始dfs,不断比较更新全局变量即可

int res=0;
int maxPath(TreeNode *root) //以root为路径起始点的最长路径
{
    if (!root)
        return 0;
    int left=maxPath(root->left);
    int right=maxPath(root->right);
    res = max(res, left + right + root->val); //更新全局变量
    return max(left, right);   //返回左右路径较长者
}

这类题型DFS注意点:

  1. left,right代表的含义要根据题目所求设置,比如最长路径、最大路径和等等

  2. 全局变量res的初值设置是0还是INT_MIN要看题目节点是否存在负值,如果存在就用INT_MIN,否则就是0

  3. 注意两点之间路径为1,因此一个点是不能构成路径的

经典题目

  1. 94. Binary Tree Inorder Traversal

  2. 95. Unique Binary Search Trees II

  3. 96. 不同的二叉搜索树

  4. 98. Validate Binary Search Tree

  5. 99. Recover Binary Search Tree

  6. 100. Same Tree

  7. 101. Symmetric Tree

  8. 102. 二叉树的层序遍历

  9. 103. Binary Tree Zigzag Level Order Traversal

  10. 104. Maximum Depth of Binary Tree

  11. 105. Construct Binary Tree from Preorder and Inorder Traversal

  12. 106. Construct Binary Tree from Inorder and Postorder Traversal

  13. 107. Binary Tree Level Order Traversal II

  14. 108. 将有序数组转换为二叉搜索树

  15. 109. 有序链表转换二叉搜索树

  16. 110. Balanced Binary Tree

  17. 111. Minimum Depth of Binary Tree

  18. 112. Path Sum

  19. 113. Path Sum II

  20. 114. Flatten Binary Tree to Linked List

  21. 116. Populating Next Right Pointers in Each Node

  22. 117. Populating Next Right Pointers in Each Node II

  23. 124. 二叉树中的最大路径和

  24. 129. Sum Root to Leaf Numbers

  25. 144. Binary Tree Preorder Traversal

  26. 145. Binary Tree Postorder Traversal

  27. [0156-binary-tree-upside-down]

  28. [0173-binary-search-tree-iterator]

  29. 199. Binary Tree Right Side View

  30. 222. Count Complete Tree Nodes

  31. 226. Invert Binary Tree

  32. 230. Kth Smallest Element in a BST

  33. 235. Lowest Common Ancestor of a Binary Search Tree

  34. 236. 二叉树的最近公共祖先

  35. [0250-count-univalue-subtrees]

  36. [0255-verify-preorder-sequence-in-binary-search-tree]

  37. 257. Binary Tree Paths

  38. [0270-closest-binary-search-tree-value]

  39. [0272-closest-binary-search-tree-value-ii]

  40. [0285-inorder-successor-in-bst]

  41. 297. Serialize and Deserialize Binary Tree

  42. [0298-binary-tree-longest-consecutive-sequence]

  43. [0314-binary-tree-vertical-order-traversal]

  44. [0331-verify-preorder-serialization-of-a-binary-tree]

  45. [0333-largest-bst-subtree]

  46. 337. 打家劫舍 III

  47. 341. Flatten Nested List Iterator

  48. [0366-find-leaves-of-binary-tree]

  49. 404. Sum of Left Leaves

  50. [0426-convert-binary-search-tree-to-sorted-doubly-linked-list]

  51. [0427-construct-quad-tree]

  52. [0428-serialize-and-deserialize-n-ary-tree]

  53. 429. N-ary Tree Level Order Traversal

  54. [0431-encode-n-ary-tree-to-binary-tree]

  55. 437. Path Sum III

  56. [0449-serialize-and-deserialize-bst]

  57. 450. Delete Node in a BST

  58. 501. Find Mode in Binary Search Tree

  59. [0508-most-frequent-subtree-sum]

  60. [0510-inorder-successor-in-bst-ii]

  61. 513. Find Bottom Left Tree Value

  62. 515. Find Largest Value in Each Tree Row

  63. 530. 二叉搜索树的最小绝对差

  64. [0536-construct-binary-tree-from-string]

  65. 538. Convert BST to Greater Tree

  66. 543. Diameter of Binary Tree

  67. [0545-boundary-of-binary-tree]

  68. [0549-binary-tree-longest-consecutive-sequence-ii]

  69. [0558-logical-or-of-two-binary-grids-represented-as-quad-trees]

  70. 559. Maximum Depth of N-ary Tree

  71. [0563-binary-tree-tilt]

  72. [0572-subtree-of-another-tree]

  73. [0582-kill-process]

  74. [0589-n-ary-tree-preorder-traversal]

  75. [0590-n-ary-tree-postorder-traversal]

  76. [0606-construct-string-from-binary-tree]

  77. 617. Merge Two Binary Trees

  78. [0623-add-one-row-to-tree]

  79. 637. Average of Levels in Binary Tree

  80. [0652-find-duplicate-subtrees]

  81. [0653-two-sum-iv-input-is-a-bst]

  82. 654. Maximum Binary Tree

  83. [0655-print-binary-tree]

  84. 662. 二叉树最大宽度

  85. [0663-equal-tree-partition]

  86. [0666-path-sum-iv]

  87. 669. Trim a Binary Search Tree

  88. [0671-second-minimum-node-in-a-binary-tree]

  89. [0687-longest-univalue-path]

  90. [0690-employee-importance]

  91. 700. Search in a Binary Search Tree

  92. 701. Insert into a Binary Search Tree

  93. [0703-kth-largest-element-in-a-stream]

  94. [0742-closest-leaf-in-a-binary-tree]

  95. [0776-split-bst]

  96. [0783-minimum-distance-between-bst-nodes]

  97. [0814-binary-tree-pruning]

  98. [0834-sum-of-distances-in-tree]

  99. [0863-all-nodes-distance-k-in-binary-tree]

  100. [0865-smallest-subtree-with-all-the-deepest-nodes]

  101. [0872-leaf-similar-trees]

  102. [0889-construct-binary-tree-from-preorder-and-postorder-traversal]

  103. [0894-all-possible-full-binary-trees]

  104. [0897-increasing-order-search-tree]

  105. [0919-complete-binary-tree-inserter]

  106. [0938-range-sum-of-bst]

  107. [0951-flip-equivalent-binary-trees]

  108. [0958-check-completeness-of-a-binary-tree]

  109. [0965-univalued-binary-tree]

  110. [0968-binary-tree-cameras]

  111. [0971-flip-binary-tree-to-match-preorder-traversal]

  112. [0979-distribute-coins-in-binary-tree]

  113. [0987-vertical-order-traversal-of-a-binary-tree]

  114. [0988-smallest-string-starting-from-leaf]

  115. [0993-cousins-in-binary-tree]

  116. [0998-maximum-binary-tree-ii]

  117. [1008-construct-binary-search-tree-from-preorder-traversal]

  118. [1022-sum-of-root-to-leaf-binary-numbers]

  119. [1026-maximum-difference-between-node-and-ancestor]

  120. [1028-recover-a-tree-from-preorder-traversal]

  121. [1038-binary-search-tree-to-greater-sum-tree]

  122. [1080-insufficient-nodes-in-root-to-leaf-paths]

  123. [1104-path-in-zigzag-labelled-binary-tree]

  124. 1110. Delete Nodes And Return Forest

  125. [1120-maximum-average-subtree]

  126. [1123-lowest-common-ancestor-of-deepest-leaves]

  127. [1145-binary-tree-coloring-game]

  128. [1161-maximum-level-sum-of-a-binary-tree]

  129. [1214-two-sum-bsts]

  130. [1245-tree-diameter]

  131. [1257-smallest-common-region]

  132. [1261-find-elements-in-a-contaminated-binary-tree]

  133. [1273-delete-tree-nodes]

  134. [1302-deepest-leaves-sum]

  135. [1305-all-elements-in-two-binary-search-trees]

  136. [1315-sum-of-nodes-with-even-valued-grandparent]

  137. [1325-delete-leaves-with-a-given-value]

  138. [1339-maximum-product-of-splitted-binary-tree]

  139. [1361-validate-binary-tree-nodes]

  140. [1367-linked-list-in-binary-tree]

  141. [1372-longest-zigzag-path-in-a-binary-tree]

  142. [1373-maximum-sum-bst-in-binary-tree]

  143. [1376-time-needed-to-inform-all-employees]

  144. [1377-frog-position-after-t-seconds]

  145. [1379-find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree]

  146. [1382-balance-a-binary-search-tree]

  147. [1430-check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree]

  148. [1443-minimum-time-to-collect-all-apples-in-a-tree]

  149. [1448-count-good-nodes-in-binary-tree]

  150. [1457-pseudo-palindromic-paths-in-a-binary-tree]

  151. [1469-find-all-the-lonely-nodes]

  152. [1483-kth-ancestor-of-a-tree-node]

  153. [1485-clone-binary-tree-with-random-pointer]

  154. [1490-clone-n-ary-tree]

  155. [1506-find-root-of-n-ary-tree]

  156. [1516-move-sub-tree-of-n-ary-tree]

  157. [1519-number-of-nodes-in-the-sub-tree-with-the-same-label]

  158. [1522-diameter-of-n-ary-tree]

  159. [1530-number-of-good-leaf-nodes-pairs]

  160. [1569-number-of-ways-to-reorder-array-to-get-same-bst]

  161. [1586-binary-search-tree-iterator-ii]

  162. [1597-build-binary-expression-tree-from-infix-expression]

  163. [1600-throne-inheritance]

  164. [1602-find-nearest-right-node-in-binary-tree]

  165. [1609-even-odd-tree]

  166. [1612-check-if-two-expression-trees-are-equivalent]

  167. [1617-count-subtrees-with-max-distance-between-cities]

  168. [1628-design-an-expression-tree-with-evaluate-function]

  169. 1644. Lowest Common Ancestor of a Binary Tree II

  170. 1650. Lowest Common Ancestor of a Binary Tree III

  171. [1660-correct-a-binary-tree]

  172. [1666-change-the-root-of-a-binary-tree]

  173. [1676-lowest-common-ancestor-of-a-binary-tree-iv]

  174. [1719-number-of-ways-to-reconstruct-a-tree]

  175. [1740-find-distance-in-a-binary-tree]

  176. [1766-tree-of-coprimes]

  177. [1902-depth-of-bst-given-insertion-order]

  178. [1916-count-ways-to-build-rooms-in-an-ant-colony]

  179. [1932-merge-bsts-to-create-single-bst]

  180. [1973-count-nodes-equal-to-sum-of-descendants]

  181. [1993-operations-on-tree]

  182. [2003-smallest-missing-genetic-value-in-each-subtree]

  183. [2005-subtree-removal-game-with-fibonacci-tree]

  184. [2049-count-nodes-with-the-highest-score]

  185. [2096-step-by-step-directions-from-a-binary-tree-node-to-another]

  186. [2196-create-binary-tree-from-descriptions]

  187. [2236-root-equals-sum-of-children]

  188. [2246-longest-path-with-different-adjacent-characters]

  189. [2265-count-nodes-equal-to-average-of-subtree]

  190. [2277-closest-node-to-path-in-tree]

  191. [2313-minimum-flips-in-binary-tree-to-get-result]

  192. [2322-minimum-score-after-removals-on-a-tree]

  193. [2331-evaluate-boolean-binary-tree]

  194. [2368-reachable-nodes-with-restrictions]

  195. [2378-choose-edges-to-maximize-score-in-a-tree]

  196. [2385-amount-of-time-for-binary-tree-to-be-infected]

  197. [2415-reverse-odd-levels-of-binary-tree]

  198. [2421-number-of-good-paths]

  199. [2440-create-components-with-same-value]

  200. [2445-number-of-nodes-with-value-one]

  201. [2458-height-of-binary-tree-after-subtree-removal-queries]

  202. [2467-most-profitable-path-in-a-tree]

  203. [2471-minimum-number-of-operations-to-sort-a-binary-tree-by-level]

  204. [2476-closest-nodes-queries-in-a-binary-search-tree]

  205. [2477-minimum-fuel-cost-to-report-to-the-capital]

  206. [2479-maximum-xor-of-two-non-overlapping-subtrees]

  207. [2509-cycle-length-queries-in-a-tree]

  208. [2538-difference-between-maximum-and-minimum-price-sum]

  209. [2581-count-number-of-possible-root-nodes]

  210. [2583-kth-largest-sum-in-a-binary-tree]

  211. [2603-collect-coins-in-a-tree]

  212. [2641-cousins-in-binary-tree-ii]

  213. [2646-minimize-the-total-price-of-the-trips]

  214. [2673-make-costs-of-paths-equal-in-a-binary-tree]

  215. [2689-extract-kth-character-from-the-rope-tree]

  216. [2764-is-array-a-preorder-of-some-binary-tree]

  217. [2773-height-of-special-binary-tree]

  218. [2791-count-paths-that-can-form-a-palindrome-in-a-tree]

  219. [2792-count-nodes-that-are-great-enough]

  220. [2846-minimum-edge-weight-equilibrium-queries-in-a-tree]

  221. [2867-count-valid-paths-in-a-tree]

  222. [2872-maximum-number-of-k-divisible-components]

  223. [2920-maximum-points-after-collecting-coins-from-all-nodes]

  224. [2925-maximum-score-after-applying-operations-on-a-tree]

  225. [2973-find-number-of-coins-to-place-in-tree-nodes]

  226. [3004-maximum-subtree-of-the-same-color]

  227. [3067-count-pairs-of-connectable-servers-in-a-weighted-tree-network]

  228. [3068-find-the-maximum-sum-of-node-values]

  229. [3157-find-the-level-of-tree-with-minimum-sum]

  230. [3203-find-minimum-diameter-after-merging-two-trees]

  231. [3241-time-taken-to-mark-all-nodes]

  232. [3249-count-the-number-of-good-nodes]

  233. [3313-find-the-last-marked-nodes-in-tree]

  234. [3319-k-th-largest-perfect-subtree-size-in-binary-tree]

  235. [3327-check-if-dfs-strings-are-palindromes]

  236. [3331-find-subtree-sizes-after-changes]

  237. [3367-maximize-sum-of-weights-after-edge-removals]

  238. [3372-maximize-the-number-of-target-nodes-after-connecting-trees-i]

  239. [3373-maximize-the-number-of-target-nodes-after-connecting-trees-ii]

  240. [3425-longest-special-path]

  241. [3486-longest-special-path-ii]