[{"type":"Paragraph","children":[{"text":"稍微记了点……还得多复习回溯和Dfs 的相关"}],"slateId":"qNZSl_H9y1rDp2lqZXD2Q"},{"type":"Paragraph","slateId":"GMoujzxJq7XQ8to3R2M1g","children":[{"text":"DFS 复习： "}]},{"type":"Paragraph","slateId":"cwQV9ya3rJKZNgXrhKjtm","children":[{"text":"一基础"}]},{"type":"Paragraph","slateId":"2YbZ66OX3TpyJGlZkSjH5","children":[{"text":""}]},{"type":"Paragraph","slateId":"gb73cpcifsfLJM25Pcn3l","children":[{"text":"Q94 中序遍历: 左根右到了 child node tree也是左 child 右边"}]},{"type":"Paragraph","slateId":"9nHU-5SPKltGBCsGN0AUa","children":[{"text":"注意："}]},{"type":"Paragraph","slateId":"lNwTd7t95_D5E8aQT0ISC","children":[{"text":"\u0001 3在2 前面直到null 才return 逐层加上值所以 3（left right both null）return--> 2(right null return)-->1 3 2"}]},{"type":"Paragraph","slateId":"xoMPdkZmxvM2SY56kcLln","children":[{"text":" private void inOrder(TreeNode root){"}]},{"type":"Paragraph","slateId":"c9NHIsFC1QQKOt2Bm3C9O","children":[{"text":" "}]},{"type":"Paragraph","slateId":"1ioTKoUvAWwdD10eUgkGX","children":[{"text":" if(root==null) return;"}]},{"type":"Paragraph","slateId":"dFjkk6_DkTsXQ7CdZP8xG","children":[{"text":" inOrder(root.left);"}]},{"type":"Paragraph","slateId":"5FeBOyTiXa26Rt3tlV8WC","children":[{"text":" rec.add(root.val);"}]},{"type":"Paragraph","slateId":"9troKe0P3TT4-kfMwReaS","children":[{"text":" inOrder(root.right);"}]},{"type":"Paragraph","slateId":"6xOijJwEQoflJ1WY8dlTJ","children":[{"text":""}]},{"type":"Paragraph","slateId":"gyRgwfZZ-PQl8tE6fIKKW","children":[{"text":"Q144 前序遍历 root 先行其他类似"}]},{"type":"Paragraph","slateId":"yFwCPvg8YeSWSoaCG1oSh","children":[{"text":" if(root==null)return;"}]},{"type":"Paragraph","slateId":"xS3sXyZWyXemcfWuXY6iD","children":[{"text":" li.add(root.val);"}]},{"type":"Paragraph","slateId":"72Eiw6E33atrR-GpVyybQ","children":[{"text":" preorderRec(root.left,li);"}]},{"type":"Paragraph","slateId":"1mKsfdDz454C9R_4dai2G","children":[{"text":" preorderRec(root.right, li);"}]},{"type":"Paragraph","slateId":"mLtUU4UzJXgagCux4JwFx","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"sT8mzrSCssVgMhfzEmKJD","children":[{"text":"\u0001"}]},{"type":"Paragraph","slateId":"xSFQP-BRRSF9BYALozo0B","children":[{"text":"输入：root = [1,2,3,4,5,null,8,null,null,6,7,9] 输出：[1,2,4,5,6,7,3,8,9]"}]},{"type":"Paragraph","slateId":"gFmBnsu3Kz6CxnQ2HcBUg","children":[{"text":""}]},{"type":"Paragraph","slateId":"7amFsS5c0XqbEza5vcZPQ","children":[{"text":"Q 872. 叶子相似的树用前序遍历Dfs 类似的方法 "}]},{"type":"Paragraph","slateId":"Q-nNigVXZ6gumu3wF7fVI","children":[{"text":"list1.equals.(list 2)可以测两相等"}]},{"type":"Paragraph","slateId":"UtcX7xBx1xPLc1m5tEkWi","children":[{"text":"QLCP 44. 开幕式焰火用Set避免重复"}]},{"type":"Paragraph","slateId":"GkT4jCd4uBbxAudgQFB4n","children":[{"text":"Q404. 左叶子之和"}]},{"type":"Paragraph","slateId":"TvCl4vi85x9u4Xc5UiAth","children":[{"text":"Q671二叉树中第二小的节点"}]},{"type":"Paragraph","slateId":"PonDWAPLxO7QH-uTyyjtv","children":[{"text":" private void dfs(TreeNode node){"}]},{"type":"Paragraph","slateId":"xqxWvJmJKO9T32ANbWNF1","children":[{"text":" if(node==null)return;"}]},{"type":"Paragraph","slateId":"9poGRCtBkBlIx2uyykUir","children":[{"text":""}]},{"type":"Paragraph","slateId":"hFIQpEXOezmDtYuys_ohR","children":[{"text":" if(ans!=-1 &&node.val>=ans)return; // 由于数列并不是单调递增的，可能在很后面 aka level大的时候，仍然出现第二大的值 eg 1 3 ....... 8 6 5 2 所以需要"}]},{"type":"Paragraph","slateId":"aDmEwlPtIcK4Vm3FUwQJt","children":[{"text":" "}]},{"type":"Paragraph","slateId":"2WfLa41U1EbAtKh77x8V6","children":[{"text":" if(node.val>rval) ans=node.val; 找到大于根值的树更新而不是直接复制到rval上，因为"}]},{"type":"Paragraph","slateId":"nAaZm_D1qQrkvio6pjJBL","children":[{"text":" dfs(node.left);"}]},{"type":"Paragraph","slateId":"cdXcnAIAMHf8sBPM7Su0-","children":[{"text":" dfs(node.right);"}]},{"type":"Paragraph","slateId":"sozx_JZ8mj5bFd7BHJg1A","children":[{"text":""}]},{"type":"Paragraph","slateId":"KgV-Ir2K5YRLgKf1X8P5b","children":[{"text":"§2.3 自底向上 DFS（后序遍历）"}]},{"type":"Paragraph","slateId":"YVDY5Qm92XdYml-VDALYu","children":[{"text":"Q104. 二叉树的最大深度:"}]},{"type":"Paragraph","slateId":"vbFpa2gzEuQJlEimZ-Fwm","children":[{"text":" 数量类return dfs, "}]},{"type":"Paragraph","slateId":"-z1w-xgC4XyQ1R5mJE9Et","children":[{"text":"后序： 1 初始态 2 叠加 3 最后Return 可能包含单独单位态在这里进行运算（+1）是先到leaf节点再开始运算Leaf节点结果 etc"}]},{"type":"Paragraph","slateId":"rW6Huorz2H6grL7QDRYh8","children":[{"text":"1 自底而上，后序遍历 public int maxDepth(TreeNode root) {"}]},{"type":"Paragraph","slateId":"Jy_Tpow8UDpV5sYh-NtU9","children":[{"text":" if(root==null){"}]},{"type":"Paragraph","slateId":"d2aExWXowDN3p61BX-hTv","children":[{"text":" return 0;"}]},{"type":"Paragraph","slateId":"ovwq2T7h29fY3ZIkNCYhJ","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"uBLnbDux5C8UaEhME2uU6","children":[{"text":" int leftH = maxDepth(root.left);"}]},{"type":"Paragraph","slateId":"z2esgLFDH1fPR0FAI6TlS","children":[{"text":" int rightH= maxDepth(root.right);"}]},{"type":"Paragraph","slateId":"BoiU-CKEDksbcMwZ9UAJ7","children":[{"text":" return Math.max(leftH,rightH)+1;}"}]},{"type":"Paragraph","slateId":"nu0ef7ovZ4hgvJu6WtsjF","children":[{"text":" 注意 return Math.max (leftHeigh, rightH) + 1; 只在这里开始计算高度，其他都是recursion 的方式"}]},{"type":"Paragraph","slateId":"jmXC6vyR0D44R_JBL_OHZ","children":[{"text":"2 按之前的自顶而下前序遍历先更改depth ans(注意 depth=1 才是root depth 所以需要先加。此题里是先加不是在recursion 里++，"}]},{"type":"Paragraph","slateId":"DMLC6zQ4IgPlm8HAzTysj","children":[{"text":" int ans;"}]},{"type":"Paragraph","slateId":"m3LbpL5MMgyW70_RqoTEx","children":[{"text":" public int maxDepth(TreeNode root) {"}]},{"type":"Paragraph","slateId":"U6_BVzhEtSLk14ZRNsRin","children":[{"text":" topDownDFS(root,0);"}]},{"type":"Paragraph","slateId":"1OGoYdyHgNz9tzSSZK_lG","children":[{"text":" return ans;"}]},{"type":"Paragraph","slateId":"_FytGs_qz_Xo4ByhL31Q_","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"EwANWL80d1X8_qyRFr18Z","children":[{"text":" private void topDownDFS(TreeNode root, int depth){"}]},{"type":"Paragraph","slateId":"EL3a6PfV9eiYf46KZfczf","children":[{"text":" if(root==null) return;"}]},{"type":"Paragraph","slateId":"hZxC5chKhz2-ovWhPwxWC","children":[{"text":""}]},{"type":"Paragraph","slateId":"5r6tzF03rqeBEK_aAOr8K","children":[{"text":" depth++;"}]},{"type":"Paragraph","slateId":"Th1P8Fr1EfKctcn_LY3sW","children":[{"text":" ans=Math.max(ans, depth);"}]},{"type":"Paragraph","slateId":"XG0lM-o2nQZ8EGqIEdPGd","children":[{"text":" topDownDFS(root.left, depth);"}]},{"type":"Paragraph","slateId":"CVORxFhWB7hFoDdkQttbC","children":[{"text":" topDownDFS(root.right,depth);"}]},{"type":"Paragraph","slateId":"vUZM5TgCLXjWbw6c2mhCp","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"InWMptSDQRqdYDdwGdCJx","children":[{"text":""}]},{"type":"Paragraph","slateId":"PoNJUDeTKqxA3ufCaeWPF","children":[{"text":""}]},{"type":"Paragraph","slateId":"K4lD-TI-Me66sXHnv_EnS","children":[{"text":"Q111. 二叉树的最小深度"}]},{"type":"Paragraph","slateId":"6U9WQS3jZwrzcir2ZF8q4","children":[{"text":"注意不能在 right==null 的时候，赋值left= mind + 1 right = mind+1, "}]},{"type":"Paragraph","slateId":"x7qJ1ojrAWmLnEGH5A_ix","children":[{"text":"在这类题中最好避免中间和结尾Return同时 +1 会有所重复"}]},{"type":"Paragraph","slateId":"hRXsvCJZx1CzeBuqr0CBh","children":[{"text":"或者 left = mind, right = mind"}]},{"type":"Paragraph","slateId":"kTU5SeTVi89AfXtcw9hma","children":[{"text":" public int minDepth(TreeNode root) {"}]},{"type":"Paragraph","slateId":"oqEE_myUPlDKKxf068nmd","children":[{"text":" if(root==null)return 0;"}]},{"type":"Paragraph","slateId":"tqq759exK0adystzbggdX","children":[{"text":""}]},{"type":"Paragraph","slateId":"X6_aMNUlAg7-RvtC8eHKV","children":[{"text":" int leftMin=minDepth(root.left); "}]},{"type":"Paragraph","slateId":"qiMJ9-T4OAp4FofCWqHvM","children":[{"text":" int rightMin=minDepth(root.right); "}]},{"type":"Paragraph","slateId":"bp63g6h_ENFd2qW_L4g8P","children":[{"text":" "}]},{"type":"Paragraph","slateId":"1nL9jaqJwQB889e3u4UTj","children":[{"text":" return (leftMin==0|| rightMin==0)?(leftMin + rightMin + 1): Math.min(leftMin, rightMin)+1;//由于要到Leaf 如若一个零一个不为零，则选择 0+ 存在的那个+1"}]},{"type":"Paragraph","slateId":"uatRYAhcPWg8-2XO0eNJ4","children":[{"text":"亦或是"}]},{"type":"Paragraph","slateId":"qC_F9-feKMU9_Ut9kQDF4","children":[{"text":" if(root==null)return 0;"}]},{"type":"Paragraph","slateId":"6pQ4wtBWxsUnIZZ99pXWf","children":[{"text":""}]},{"type":"Paragraph","slateId":"VH1XI6HE3RS8DMMUmGeAO","children":[{"text":" if(root.left==null &&root.right==null) return 1;到叶子开始计算"}]},{"type":"Paragraph","slateId":"Clbr8g60zGD60Ft0fPL7L","children":[{"text":""}]},{"type":"Paragraph","slateId":"jg7qoAu7QDdafXqa2Lq2V","children":[{"text":" int mindep= Integer.MAX_VALUE;"}]},{"type":"Paragraph","slateId":"vSc6bkicRfWbx-FsLCw-A","children":[{"text":""}]},{"type":"Paragraph","slateId":"CwkcFNtPO3WbRdLZlCYJo","children":[{"text":" if(root.left!=null) mindep = Math.min(minDepth(root.left), mindep);"}]},{"type":"Paragraph","slateId":"4BlRBc-fxOiJ_LtUq_fzd","children":[{"text":" if(root.right!=null) mindep = Math.min(minDepth(root.right), mindep);"}]},{"type":"Paragraph","slateId":"2FOPau6uT8k0S1aj3n6Cq","children":[{"text":""}]},{"type":"Paragraph","slateId":"8SG2prsG_BS7UixnK8y3P","children":[{"text":" return mindep+1;从叶子往上每上一层每次计算"}]},{"type":"Paragraph","slateId":"iNgXe539Uf1LjCccZT_4k","children":[{"text":""}]},{"type":"Paragraph","slateId":"wwjRwa7Ll0EP9iEb5tcLV","children":[{"text":"Q112路径总和"}]},{"type":"Paragraph","slateId":"9KtLg9HvD84JPg5uqp3it","children":[{"text":"基础题中重点多背住"}]},{"type":"Paragraph","slateId":"JbkT-f6bXGIntPQ6HrdOF","children":[{"text":"1 DFS 基础递归逐个减去途经过的 Node值直到 leaf "}]},{"type":"Paragraph","slateId":"p6rZ2KpVGGtaQflZjCdj4","children":[{"text":"leaf 值= 余下的targetsum 则可以清零路径和为tsum"}]},{"type":"Paragraph","slateId":"334D2stD2p1wdiLvO2yTV","children":[{"text":" if(root==null)return false; "}]},{"type":"Paragraph","slateId":"c_3JXsowhiB＊＊＊QYvFPVk","children":[{"text":" "}]},{"type":"Paragraph","slateId":"TheWyn-Hbz52JDbl9epTc","children":[{"text":" if(root.left==null&&root.right==null) return targetSum==root.val;"}]},{"type":"Paragraph","slateId":"zeQNPdqAjmzkSZJrKzwYP","children":[{"text":" "}]},{"type":"Paragraph","slateId":"soIPeOBGsupKVqFPHdmOo","children":[{"text":" return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);"}]},{"type":"Paragraph","slateId":"rWK3eMhkU0dvxo4iOrUEz","children":[{"text":""}]},{"type":"Paragraph","slateId":"gX60BfzSg9wGQXrsiaYBu","children":[{"text":"2 BFS用 deque stack LIFO"}]},{"type":"Paragraph","slateId":"vrK3RMXP0kGCv4t-efcMc","children":[{"text":"DFS 用 FIFO"}]},{"type":"Paragraph","slateId":"UUluY2JtGBmUnvRMLn4Co","children":[{"text":"queue.offer(new Pair<>(root,root.val));//记得 new pair格式"}]},{"type":"Paragraph","slateId":"cAmw-WhjKyhdWDOk0XqGH","children":[{"text":"TreeNode node = pair.getKey(); int pathSum = pair.getValue();"}]},{"type":"Paragraph","slateId":"4j8U6LQT0eWR9P4ja5SIG","children":[{"text":""}]},{"type":"Paragraph","slateId":"u7_zLKYSDmd0K3msvSEyj","children":[{"text":"Q199. 二叉树的右视图站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。"}]},{"type":"Paragraph","slateId":"4V68szIBrNVNU1HLloFWA","children":[{"text":"DFS 先右后左"}]},{"type":"Paragraph","slateId":"AKBWmTZpUMILhGbdsNuuR","children":[{"text":" List ans = new ArrayList<>();"}]},{"type":"Paragraph","slateId":"rX_b9UALW6TAz8UBiS6wU","children":[{"text":" dfs(root,0,ans);"}]},{"type":"Paragraph","slateId":"WK0qbEDtuKg8VIIF8bITE","children":[{"text":" return ans;"}]},{"type":"Paragraph","slateId":"EUGTpg83MJa-iv3HlsxBw","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"NszI86St81RroJH_y6ROq","children":[{"text":" private void dfs(TreeNode root, int depth,List ans){"}]},{"type":"Paragraph","slateId":"TtaUKggRnrfBNyV6ieZb7","children":[{"text":" if (root == null) {"}]},{"type":"Paragraph","slateId":"Jh6wCnC4ezb9S6D6gM-Yf","children":[{"text":" return;"}]},{"type":"Paragraph","slateId":"H6METsOZzeGv_apVXvtFx","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"UCwzSRanA6NC5EyNKPk9Z","children":[{"text":" if(depth==ans.size()){ //第一次到此depth"}]},{"type":"Paragraph","slateId":"nDwHqFsm64hiX6-yf6cxX","children":[{"text":" ans.add(root.val);"}]},{"type":"Paragraph","slateId":"gTEjHrDMdK-S2ICdLP0Ng","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"dFFu8sEsk9eCINicNeiAB","children":[{"text":" dfs(root.right, depth+1,ans);//先右后左"}]},{"type":"Paragraph","slateId":"hJaGVIlIcf4xk1PsszvHA","children":[{"text":" dfs(root.left, depth+1,ans);"}]},{"type":"Paragraph","slateId":"acAID_Okc7KfdV088NnpS","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"nXerQ-m1RRKb2KzmFjZoh","children":[{"text":"2、灵活运用BFS 关键例题**记得BFS 的遍历做法"}]},{"type":"Paragraph","slateId":"AvT7ffbfu9gBcJmXYc5S-","children":[{"text":"逐层遍历记录每层size size 清零则下一层开始先right 后left in queue , "}]},{"type":"Paragraph","slateId":"KCTDqOplY48I0NNPgv9N6","children":[{"text":"并且在size ==tmp 即此层未开始减少的时候，用ans记录第一个放进的最右值"}]},{"type":"Paragraph","slateId":"gwEvvyF_oX6H5r10nSRwT","children":[{"text":" Deque deq = new ArrayDeque<>();"}]},{"type":"Paragraph","slateId":"V8lvJYROSoKVY7eeS_k9_","children":[{"text":" deq.offer(root);"}]},{"type":"Paragraph","slateId":"ShKGNjfln8Cq4I71bLb-c","children":[{"text":""}]},{"type":"Paragraph","slateId":"vhxpy3v_S-UblFEdOMQr5","children":[{"text":" while(!deq.isEmpty()){"}]},{"type":"Paragraph","slateId":"dLO47nlsSSuSeRbBitGYZ","children":[{"text":" int siz = deq.size();"}]},{"type":"Paragraph","slateId":"2eP-4-B5lQmWS5tsvn76G","children":[{"text":" int tmp = siz;"}]},{"type":"Paragraph","slateId":"rJgBbAAH4UaYSerHm_mKZ","children":[{"text":" while(siz>0){"}]},{"type":"Paragraph","slateId":"dVn9JsHr4P5fI7FdEeMKv","children":[{"text":" TreeNode node = deq.poll();"}]},{"type":"Paragraph","slateId":"ammJYukQNRJjotg-LAa4U","children":[{"text":" if(siz==tmp) ans.add(node.val);"}]},{"type":"Paragraph","slateId":"TlBEyP8iTl7vct6ZxMKrf","children":[{"text":" if(node.right!=null){"}]},{"type":"Paragraph","slateId":"NFbRHyYO_5lidAyJNHhyl","children":[{"text":" deq.offer(node.right);"}]},{"type":"Paragraph","slateId":"FDR2B4fyyzqFCRxXAEjcb","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"B_XpO2VgxbmJlPqX4aped","children":[{"text":" if(node.left!=null){"}]},{"type":"Paragraph","slateId":"NonsG_AbFxYDflFzthZ7K","children":[{"text":" deq.offer(node.left);"}]},{"type":"Paragraph","slateId":"9krEues4lb_FATADejbd0","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"-8ulAbhoOTYgK8-GdLWeX","children":[{"text":" siz--;"}]},{"type":"Paragraph","slateId":"dbhUWY6YcjFzk2zQm6UOJ","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"rLSQglW1hXTLfMKvnU39C","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"cgytjINucN_UxAE1BaP2U","children":[{"text":" return ans;"}]},{"type":"Paragraph","slateId":"Moh59eJ5N7ro3fmEyxChI","children":[{"text":"Q129. 求根节点到叶节点数字之和数字型 "}]},{"type":"Paragraph","slateId":"bSePKT9x9GNqAauI9ldx8","children":[{"text":"1当到末尾null return 0"}]},{"type":"Paragraph","slateId":"pSnxzZClIDIC0h5S3knex","children":[{"text":" 2 计算 X=x*10+node.val"}]},{"type":"Paragraph","slateId":"cfUCRyk4MwgglmBxKjwRA","children":[{"text":"3 当到了leaf return X"}]},{"type":"Paragraph","slateId":"7IuUlIA9AzfhIp521VouW","children":[{"text":" private int dfs(TreeNode node, int x){"}]},{"type":"Paragraph","slateId":"yYOAFV7ah8U36b4U0v-T8","children":[{"text":" if(node==null)return 0;"}]},{"type":"Paragraph","slateId":"rhQgrWmMFz6su-sICS-Xd","children":[{"text":" //x is previous value"}]},{"type":"Paragraph","slateId":"84kZvjWjLSpE3CntKsEuZ","children":[{"text":" x=x*10+node.val;"}]},{"type":"Paragraph","slateId":"kC1XvPev8FmLMBurdtUYa","children":[{"text":" if(node.left==null&&node.right==null){"}]},{"type":"Paragraph","slateId":"KyBenrMBf5r2y2XDHcfE9","children":[{"text":" return x;"}]},{"type":"Paragraph","slateId":"RacbWhZ2uOFvNMWsA-BMa","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"FOSXFgIFjRmsHyFjOKkAg","children":[{"text":" return dfs(node.left,x)+dfs(node.right,x);"}]},{"type":"Paragraph","slateId":"optm_ybr8CzdOTvmkfIhg","children":[{"text":"Q1448. 统计二叉树中好节点的数目"}]},{"type":"Paragraph","slateId":"hnQKpq3jKYQwfJ-ejU9-W","children":[{"text":"dfs 统计数量类DFS题目模板分析 ans+1 ans = dfs left + dfs right"}]},{"type":"Paragraph","slateId":"w61b4psnHnlF87RAbCPkd","children":[{"text":"在Dfs 的所有行数/loop，最上端写出的 variable eg int ans = 0 不会再被Dfs 中不断清零不断重新设立"}]},{"type":"Paragraph","slateId":"fmM6_a_4BlAVdSozACMvi","children":[{"text":" private int dfs(TreeNode root, int preMax){"}]},{"type":"Paragraph","slateId":"WtZctO-uGL220c7iOb1jF","children":[{"text":" if(root==null)return 0;"}]},{"type":"Paragraph","slateId":"Ob9WBGb1Ixis8qmWxbgx2","children":[{"text":" int ans = 0; //初始态当null时候，外加设立新变量记录结果"}]},{"type":"Paragraph","slateId":"La7e-PivcUzxvY3nhYjKF","children":[{"text":" if(root.val>=preMax){"}]},{"type":"Paragraph","slateId":"pugv9w7BzNLyHcLHjNE68","children":[{"text":" ans++;"}]},{"type":"Paragraph","slateId":"QWEqRpTowCChdz6LMXuih","children":[{"text":" preMax=root.val;"}]},{"type":"Paragraph","slateId":"LsiZmV1j_xOP0iMmSNDll","children":[{"text":" }\t\t\t\t\t\t\t//unit 单独单位态，当1 件目标事件发生，该如何操作"}]},{"type":"Paragraph","slateId":"HadUQSvPUu9hm9Ftuls9Q","children":[{"text":" ans += dfs(root.left,preMax) + dfs(root.right, preMax);"}]},{"type":"Paragraph","slateId":"cWoLfBnBD_Tl0RZAXiblg","children":[{"text":""}]},{"type":"Paragraph","slateId":"uWbEdB5BOHb956TxuEOcC","children":[{"text":" return ans; // 叠加当所有同类单位事件发生该如何统计结果 +dfs + dfs"}]},{"type":"Paragraph","slateId":"HBkAwB5OrX7qTyk6WnsVR","children":[{"text":" "}]},{"type":"Paragraph","slateId":"WKTVkr4M235WZT0m4jWrW","children":[{"text":""}]},{"type":"Paragraph","slateId":"pxBLybzOz_XSypM5hkAFI","children":[{"text":"Q1315. 祖父节点值为偶数的节点和"}]},{"type":"Paragraph","slateId":"0GmLMYPhH7_CEpK63K9on","children":[{"text":"逐层更新预设 pval gpval = 1 避免被2整除"}]},{"type":"Paragraph","slateId":"lrVktGdre80wfnQHI8xUQ","children":[{"text":" "}]},{"type":"Paragraph","slateId":"Ai5F_36UzQksvoo0oxkCA","children":[{"text":""}]},{"type":"Paragraph","slateId":"jxLvXJ3CTUx7D4x9wYhVF","children":[{"text":"Q988从叶结点开始的最小字符串"}]},{"type":"Paragraph","slateId":"3C0S8p7l1wdtbD60TW8hL","children":[{"text":"string s1.compareTo(s2):"}]},{"type":"Paragraph","slateId":"1w6AGJa8IqF1jKs3PDVvl","children":[{"text":"由于所有都是由小写字母组成，想要设立max String max=\"~\" ascii在 z 之后"}]},{"type":"Paragraph","slateId":"Fhh7RdqPgJOdU43mlUHUK","children":[{"text":"！compareTo: 字典意义上比较， if <0 s1 all letters"}]},{"type":"Paragraph","slateId":"Noqid_G7u0eQzmDa1yimJ","children":[{"text":" StringBuffer ans = new StringBuffer();"}]},{"type":"Paragraph","slateId":"0Tauq22zLzqk-Km5id1yD","children":[{"text":" public String smallestFromLeaf(TreeNode root) {"}]},{"type":"Paragraph","slateId":"U96NlXqvpxoW4QuLHJzxn","children":[{"text":" dfs(root);"}]},{"type":"Paragraph","slateId":"Tg1CQ_akAEHr83UEu-0vd","children":[{"text":" return res;"}]},{"type":"Paragraph","slateId":"PN93kjLkHmkTzyHgH_mqn","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"ArxBjGLn6MJd8wHBQLk4q","children":[{"text":" public void dfs(TreeNode root){"}]},{"type":"Paragraph","slateId":"MIDQN-DhItxuWJSn-fi8X","children":[{"text":" if(root==null) return; 初始态当null时候，"}]},{"type":"Paragraph","slateId":"63gym1Ldu3nT6q1OknjCg","children":[{"text":" //在前部插入新的char"}]},{"type":"Paragraph","slateId":"5wLgq8OVelMtLsEJjEqkW","children":[{"text":" char r = (char)('a' + root.val);格式注意 int to char"}]},{"type":"Paragraph","slateId":"aHPQqsh0YUHdLJLUXg1u-","children":[{"text":" ans.insert(0,r);"}]},{"type":"Paragraph","slateId":"5YN3VZrjtfcTzngqPbXjI","children":[{"text":""}]},{"type":"Paragraph","slateId":"3ooTEwVWlj0a-eq1cvIrV","children":[{"text":" //若当前为最小字符串，更新 unit 单独单位态，当1 件目标事件发生"}]},{"type":"Paragraph","slateId":"Vcp_YM3cRitqnHtk2RRW9","children":[{"text":" if(root.right==null &&root.left==null){"}]},{"type":"Paragraph","slateId":"rxJyi_FJc0f2gcBQtljAc","children":[{"text":" if(ans.toString().compareTo(res)<0){"}]},{"type":"Paragraph","slateId":"Gegt1OfPf0eOxmmKPkWWE","children":[{"text":" res=ans.toString();"}]},{"type":"Paragraph","slateId":"2u4ONLPp-f3VeCrZCOaJP","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"zhIyf8uidYiNTO82GlqQL","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"owaP575auzp3ShSF7zwoq","children":[{"text":" //如非leaf node 遍历"}]},{"type":"Paragraph","slateId":"w6uFarNfN3DXQI7Ljvvhk","children":[{"text":" dfs(root.left);"}]},{"type":"Paragraph","slateId":"A0f7XdgDmTjH8K_IzkeWv","children":[{"text":" dfs(root.right);叠加态当所有同类单位事件发生该如何统计结果 "}]},{"type":"Paragraph","slateId":"mSmd2-RKjTZL0D-XnIaRv","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"-lJ66kZRas6BReC7EUdBq","children":[{"text":" ans.deleteCharAt(0);//！状态重置到上一次"}]},{"type":"Paragraph","slateId":"oU4pr82zSVOVo2oimGOnq","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"dH0P8u4GmFsswhbMryRzy","children":[{"text":"Q1026. 节点与其祖先之间的最大差值"}]},{"type":"Paragraph","slateId":"7TvURtZWIDDtt9I-byGGb","children":[{"text":"每个单独的分叉路径，在dfs 的left right 分别call 里会存储单独的max min而不相交所以不担心出现 tree max- tree min = ans 的情况"}]},{"type":"Paragraph","slateId":"7i-_8L3BHCsZ7RdM4LTXo","children":[{"text":"if(root==null) {"}]},{"type":"Paragraph","slateId":"6vUCZYCMveelmMU8eV_Vk","children":[{"text":" return;// ans行写在这里然后return也可以"}]},{"type":"Paragraph","slateId":"6bKp_anSSs5GJeKZrVVWS","children":[{"text":""}]},{"type":"Paragraph","slateId":"zHayLziUy6YDQhkGme0DO","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"uNezbY-vKv9yG6OUNwMdP","children":[{"text":" mn = Math.min(mn, root.val);"}]},{"type":"Paragraph","slateId":"2lVWHQ1IvSOCEdWbOFkMv","children":[{"text":" mx = Math.max(mx, root.val);"}]},{"type":"Paragraph","slateId":"HDt-A4ch-eSw_rk9ccYsZ","children":[{"text":" ans=Math.max(ans, mx-mn);"}]},{"type":"Paragraph","slateId":"CvQYVMgzSa4FaEWGU8UNq","children":[{"text":""}]},{"type":"Paragraph","slateId":"Qj2CfJlaR7uENY44JlI2p","children":[{"text":" dfs(root.left, mn,mx);"}]},{"type":"Paragraph","slateId":"BT-6DnzczTdfYqos5-H3W","children":[{"text":" dfs(root.right, mn, mx);"}]},{"type":"Paragraph","slateId":"kfwc5MIrYSnm1plPzJVoX","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"ZcwTftfi6xEPf5wbtLaep","children":[{"text":"Q623 在二叉树中增加一行 return treenode数据型BFS public TreeNode addOneRow(TreeNode root, int val, int depth) {"}]},{"type":"Paragraph","slateId":"o99-VqKNxMORcphwvQZ05","children":[{"text":" if (root==null) return null;"}]},{"type":"Paragraph","slateId":"3m2zT2gA_UFu_vmPwMVtd","children":[{"text":" if(depth==1){"}]},{"type":"Paragraph","slateId":"_V9R7vMJTdZAkND4qOsXK","children":[{"text":" return new TreeNode(val,root,null);自己的值左node 右node"}]},{"type":"Paragraph","slateId":"jRWujQ7-7O5zanomJUwhQ","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"Cas6-ftBcF1jgHDdaPliP","children":[{"text":" if(depth==2){//下一层就需要加 vaL 原root.left 为 val 的左子树，etc"}]},{"type":"Paragraph","slateId":"e_eTOS5ABwFHRdXufonXu","children":[{"text":" "}]},{"type":"Paragraph","slateId":"8YwPo9OKXEk7duKqZi48M","children":[{"text":"root.left=new TreeNode(val, root.left, null);"}]},{"type":"Paragraph","slateId":"QGAhk1G-NgXH_S2CB13qZ","children":[{"text":" 新tnode 格式(val 左右 )"}]},{"type":"Paragraph","slateId":"iHf6aWH7Ek2bkbw9Jck0v","children":[{"text":" root.right = new TreeNode(val, null, root.right); "}]},{"type":"Paragraph","slateId":"9VVYb3qZbjL_g1ohjvlw5","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"cBusW8p9jjmL1XWMgnegq","children":[{"text":""}]},{"type":"Paragraph","slateId":"q86yRXPO6r5uwi5NorZU0","children":[{"text":" root.left = addOneRow(root.left, val, depth-1);"}]},{"type":"Paragraph","slateId":"sZVKwIDpvDKWFirMPA_Qs","children":[{"text":" root.right = addOneRow(root.right, val, depth-1);"}]},{"type":"Paragraph","slateId":"OQCF1r-iwb1yU6rs0SX8O","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"xxTOgDTIiBirbbhArA0p0","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"TfKV53if6j0ejlp5UOpQN","children":[{"text":""}]},{"type":"Paragraph","slateId":"8OKwl81_2JwiDwe4PP7Fq","children":[{"text":"Q1372 ZIGZAG 最长路径"}]},{"type":"Paragraph","slateId":"uEvINcYn4GoE9nadHaU9a","children":[{"text":" int maxL = 0;"}]},{"type":"Paragraph","slateId":"cLrv16v5cW5Sma0eZmyqD","children":[{"text":" public int longestZigZag(TreeNode root) { "}]},{"type":"Paragraph","slateId":"m9JGV53GSev03cPkt6xhT","children":[{"text":" dfs(root,true,0);"}]},{"type":"Paragraph","slateId":"uEW7TBSKBJXIIagSvumVm","children":[{"text":" dfs(root,false,0);"}]},{"type":"Paragraph","slateId":"BTuTpQnC7pQekg0zF85j2","children":[{"text":" return maxL;"}]},{"type":"Paragraph","slateId":"hpRRmDJslLlMuU4LX3iww","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"CPuFt7dj8iuydj2kZN5za","children":[{"text":" private void dfs(TreeNode root, Boolean preRight, int currL){"}]},{"type":"Paragraph","slateId":"L02tU_DS1vvQOXG5pJdb5","children":[{"text":" if(root==null)return;"}]},{"type":"Paragraph","slateId":"H34RAaQlgwssZ4zETAre5","children":[{"text":" if(preRight){"}]},{"type":"Paragraph","slateId":"qvjgBROUr7zVWdKkGetjt","children":[{"text":""}]},{"type":"Paragraph","slateId":"16ii9Hi1MbZaDPfb-dIis","children":[{"text":" //假如连续两个同向：另起此一点r.right为起点开始走"}]},{"type":"Paragraph","slateId":"QcClEGQwGKNYb0Y-i9nuw","children":[{"text":" //并且此时L清零并重新设置 =1"}]},{"type":"Paragraph","slateId":"42qIFLbb7Md1Xpeg2kPwT","children":[{"text":" if(root.right!=null){"}]},{"type":"Paragraph","slateId":"CXDZR_zlMVMPP5-iEca61","children":[{"text":" dfs(root.right,true, 1);"}]},{"type":"Paragraph","slateId":"P5MH4Zy3l79yzYGyWgFc6","children":[{"text":" } if(root.left!=null){"}]},{"type":"Paragraph","slateId":"wGxOcWhYWjh6XwjjxEUsn","children":[{"text":" dfs(root.left, false, currL+1);"}]},{"type":"Paragraph","slateId":"KtW0iq06SbhWGK1PyJBNm","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"hl1xq-p5viTVJnKAdgbCb","children":[{"text":""}]},{"type":"Paragraph","slateId":"aEX1DuCAQHJyNPS2RTzYU","children":[{"text":"Q 965 单值二叉树 boolean dfs 的return "}]},{"type":"Paragraph","slateId":"mqIligaviCSNRhHlcWFug","children":[{"text":"public boolean isUnivalTree(TreeNode root) {"}]},{"type":"Paragraph","slateId":"ZfwtJ0doe5d51aRdPwCNw","children":[{"text":"if(root==null)return true;"}]},{"type":"Paragraph","slateId":"9rlGmvyWhTTVna_CybPP9","children":[{"text":"int currVal = root.val;"}]},{"type":"Paragraph","slateId":"vXyyrZGKoJGftA0OcA5Wa","children":[{"text":" "}]},{"type":"Paragraph","slateId":"OVbTOEMR2RgKuCN5oyhcw","children":[{"text":" if(root.left!=null){"}]},{"type":"Paragraph","slateId":"2H2f--JHuBgOVvPjdcjk5","children":[{"text":" if(root.left.val!=currVal) return false;"}]},{"type":"Paragraph","slateId":"DAy0XaBCkZPTi05_tQWVY","children":[{"text":" }same right"}]},{"type":"Paragraph","slateId":"5Pl0-QNjKcP8KXGKtrcS9","children":[{"text":" return isUnivalTree(root.left)&&isUnivalTree(root.right);"}]},{"type":"Paragraph","slateId":"9nGKPSsxIx6xAlOGTGb2B","children":[{"text":"Q100 相同的树"}]},{"type":"Paragraph","slateId":"LXRQdBV3VVkECwRE7hDjm","children":[{"text":" public boolean isSameTree(TreeNode p, TreeNode q) {"}]},{"type":"Paragraph","slateId":"5FpEXfk05Ci7WEstas-KW","children":[{"text":" if(p==null&& q==null){//"}]},{"type":"Paragraph","slateId":"3Gq2IkWTISUGClnDV1Gsx","children":[{"text":" //解一原本root 就是Null 两个null =="}]},{"type":"Paragraph","slateId":"4aR1gY31Gnvpomx3MTH5Q","children":[{"text":" //解二到达单个leaf 所有通过，同时达到leaf 节点树结构一样，每个值一样。假如答案最后return true, "}]},{"type":"Paragraph","slateId":"3GvXfg8KwZo-f6MSRBawz","children":[{"text":" //则是每个Leaf 的true 累计而来"}]},{"type":"Paragraph","slateId":"6gBunrF5HVdKJF8-gq2ly","children":[{"text":" return true;"}]},{"type":"Paragraph","slateId":"zU_cZv7gIbA75B8cHbfLB","children":[{"text":" }else if(p==null || q==null){//途中树结构不一样"}]},{"type":"Paragraph","slateId":"cDxomxR_S2PCHxfVKaE9j","children":[{"text":" return false;"}]},{"type":"Paragraph","slateId":"LYaiG7zGiNOXn91fUiw36","children":[{"text":" }else if(p.val!=q.val){// 途中树 node值不一样"}]},{"type":"Paragraph","slateId":"CJlA9E790ztiPjGBWMQoY","children":[{"text":" return false;"}]},{"type":"Paragraph","slateId":"gXZp5fBum6AnayOPMv1aO","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"Oj3QX9acf8tYeLBAtXskM","children":[{"text":" return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);"}]},{"type":"Paragraph","slateId":"5e-UfHUaxCjTy4r9OVpgM","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"HHM36zWfM7IaIFcspJG9U","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"M6d6TKzmGkFWjjByS8_0w","children":[{"text":"对称二叉树类似，"}]},{"type":"Paragraph","slateId":"lokg71q_2wXIfsbLz42sq","children":[{"text":"return checktree(p.left,q.right)&&checktree( p.right ,q.left) ,"}]},{"type":"Paragraph","slateId":"PMyDtyUg870yKzR2QGifP","children":[{"text":"然后再在main 里 call check(root.left, root.right) 以同一棵树左右的子树为分别的root p ,root q."}]},{"type":"Paragraph","slateId":"3RyEiGvbxjz4K3wtuqzlA","children":[{"text":"Q 951. 翻转等价二叉树return p.val==q.val && (flipTrue || nonFlipTrue);"}]},{"type":"Paragraph","slateId":"hAEJq_ynI8VBbUck77Kku","children":[{"text":"类似上一题 flipTrue = checkTree pleft, qright && pright, qleft"}]},{"type":"Paragraph","slateId":"XM613RmaQJ4v3orBJ3FMR","children":[{"text":"boolean nonFlipTrue = check1(p.left,q.left)&&check1(p.right, q.right);"}]},{"type":"Paragraph","slateId":"vmM9SconLYzTv2mq5OV48","children":[{"text":"Q 110 平衡二叉树"}]},{"type":"Paragraph","slateId":"yWcqPVlIiSHzrcC37TsOF","children":[{"text":""}]},{"type":"Paragraph","slateId":"Bk4BM4vdcEZPfA5zL6C6V","children":[{"text":" public boolean isBalanced(TreeNode root) {"}]},{"type":"Paragraph","slateId":"oKwjUb6B0xVlnq1JxRasv","children":[{"text":" return height(root)!=-1;"}]},{"type":"Paragraph","slateId":"t0Ga9Do4XaDGEcrNfgBD5","children":[{"text":" "}]},{"type":"Paragraph","slateId":"EO6WDYj_BuwcDqt7hAdhk","children":[{"text":"}"}]},{"type":"Paragraph","slateId":"YOu0r5DQqnRKLM2eZkMvO","children":[{"text":"//递归中的归自底而上法省时间时空都是On"}]},{"type":"Paragraph","slateId":"mD6Cz1jx7owOCwnYS0dFW","children":[{"text":"public int height(TreeNode root){"}]},{"type":"Paragraph","slateId":"gNdi2tou720jlBw5sRM3_","children":[{"text":" if(root==null) return 0;"}]},{"type":"Paragraph","slateId":"2xsXL_MWWiOUwocvi9_Tc","children":[{"text":""}]},{"type":"Paragraph","slateId":"QIESqYukwUXN2cfmYmejK","children":[{"text":" int leftH = height(root.left);"}]},{"type":"Paragraph","slateId":"7-ws7Pa_puZJ8HQ2M33QJ","children":[{"text":" int rightH= height(root.right);"}]},{"type":"Paragraph","slateId":"rc4JvIJZONGEd_vvzVpmH","children":[{"text":""}]},{"type":"Paragraph","slateId":"r5XCyn4wfdPQsZ88OJW89","children":[{"text":" if(leftH ==-1 || rightH == -1 || Math.abs(leftH-rightH)>1){// 以目前节点为Root,一旦途径的左子树右子树中有一个不平衡的先例，或者一旦目前root 子树是第一个不平衡的"}]},{"type":"Paragraph","slateId":"-zbLrs-8G7ekH08scQBDC","children":[{"text":" return -1;//标记为不平衡并上传"}]},{"type":"Paragraph","slateId":"8s41lNRxjbljjmMSewvnJ","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"uOa_izSpsfJnJP54oZ4JN","children":[{"text":" return Math.max(leftH,rightH)+1;//假如度过了之前的if 平衡 1：是leaf 左右都是null max(0,0)+1 =1 "}]},{"type":"Paragraph","slateId":"woKp3TyH1GxLBOJsMpCpo","children":[{"text":" //2 假如是途中节点，以及途径过的 left rightH并非是-1, 以及左右平衡 lh-rh <=1 则继续上传，到顶部"}]},{"type":"Paragraph","slateId":"BA24MIZugznz6cDRpaklT","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"fzerUrfgjHtucEjkd9Pr8","children":[{"text":"}"}]},{"type":"Paragraph","slateId":"gNgkwwLqv1F-nRO9T4X9A","children":[{"text":""}]},{"type":"Paragraph","slateId":"2RrI-wsMBU_E9P798fBEg","children":[{"text":"Q226 翻转二叉树"}]},{"type":"Paragraph","slateId":"U_YOy0x6sFH4_48L2dbLI","children":[{"text":"在对单一树、同一树进行操作的时候，记得缓存temp 然后翻转、或者新创两个 child tree 的Root 再嫁接到原树上"}]},{"type":"Paragraph","slateId":"IU03tGUncKW54kARP9h00","children":[{"text":" public TreeNode invertTree(TreeNode root) {"}]},{"type":"Paragraph","slateId":"bLv1Tmg-JQJGyAvTSSyCc","children":[{"text":" if(root==null) return null;"}]},{"type":"Paragraph","slateId":"B-TyFCWowh7MhjIaDBB2r","children":[{"text":""}]},{"type":"Paragraph","slateId":"Wk_IagBZ1li8280o33TZV","children":[{"text":" TreeNode right= invertTree(root.left);"}]},{"type":"Paragraph","slateId":"CHr3jCUwFucM7gm18ibbL","children":[{"text":" TreeNode left= invertTree(root.right);"}]},{"type":"Paragraph","slateId":"B_96nWJrEjWqsY＊＊＊EtFu","children":[{"text":" root.right =right;"}]},{"type":"Paragraph","slateId":"pQ2se29Rhr2MYYtv8o5fJ","children":[{"text":" root.left=left;"}]},{"type":"Paragraph","slateId":"LCl5q45Q3pM59El38rmim","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"DbBxUZy_vL6sldq_8HaO6","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"fj0DJFIzFsr2JtaDwh7A2","children":[{"text":"Q 617 合并二叉树 Treenode return数据型的dfs"}]},{"type":"Paragraph","slateId":"0fEX1DZ0RqhYI14yv2qZf","children":[{"text":" public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {"}]},{"type":"Paragraph","slateId":"ahxkzkzQTmE-yHReZTiXl","children":[{"text":" return mergeT(root1, root2);"}]},{"type":"Paragraph","slateId":"Rf7yhR0ryns8iuNMNefTU","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"nkr_R1cTywEELGGx9yaB_","children":[{"text":" private TreeNode mergeT(TreeNode r1, TreeNode r2){ "}]},{"type":"Paragraph","slateId":"uMz3icGxELet5QsFuxDAb","children":[{"text":" if(r1==null) return r2;//重点空node怎么做这里是两行"}]},{"type":"Paragraph","slateId":"4fghk3o5nDkdOBq59CE5U","children":[{"text":" if(r2==null) return r1;"}]},{"type":"Paragraph","slateId":"LjAeIuzNh4eJhhqalH1x3","children":[{"text":" "}]},{"type":"Paragraph","slateId":"-uBJn5xAhBGqd-0WnrIY5","children":[{"text":" TreeNode merged = new TreeNode(r1.val+r2.val);//单位当遇到一个node怎么做、"}]},{"type":"Paragraph","slateId":"LpKvpASQ6_qK31E-wtojQ","children":[{"text":" //当有一个是空null 这次call mergeT从上而下，直接在两行If那里Return了，跳过此计算，因此node 和node value 直接上传 eg 到merged.left"}]},{"type":"Paragraph","slateId":"pdtT3DmWO7hooMPZdiGSy","children":[{"text":""}]},{"type":"Paragraph","slateId":"bKKMzObfp9aCwBe-6__or","children":[{"text":" merged.left = mergeT(r1.left,r2.left);"}]},{"type":"Paragraph","slateId":"d9g0XhavopeMee6_a-ZSj","children":[{"text":" merged.right = mergeT(r1.right, r2.right);//叠加态"}]},{"type":"Paragraph","slateId":"shQEBq-do69Ex6CWeZok0","children":[{"text":" "}]},{"type":"Paragraph","slateId":"SJmtwB9Gg6OgGaI-NayeT","children":[{"text":" return merged;"}]},{"type":"Paragraph","slateId":"OZ8W7hov5ulVcZ3vgxH6Q","children":[{"text":" "}]},{"type":"Paragraph","slateId":"8RMLf2oJjutviBUBbK3zi","children":[{"text":""}]},{"type":"Paragraph","slateId":"6MXsvCnzQdYJipSNgseI4","children":[{"text":""}]},{"type":"Paragraph","slateId":"UFsSktMr_RM_sQNqVEYCK","children":[{"text":"Q 2331 计算布尔二叉树的值 leaf 0/1 false/true 上面2/3 OR / AND 运算符"}]},{"type":"Paragraph","slateId":"Byn1e7wwA2PlDzJr2N80h","children":[{"text":" public boolean evaluateTree(TreeNode root) {"}]},{"type":"Paragraph","slateId":"kUaRVbyigbVl95uITe7A0","children":[{"text":" if(root.left==null) return root.val==1;// 自身值完整二叉树不需要测right 因为共有共无 ==1 是转为true false"}]},{"type":"Paragraph","slateId":"mowDg0r2FPZ6VXzI2yykR","children":[{"text":" if(root.val==2){"}]},{"type":"Paragraph","slateId":"3PZJTeQGgypHins9fN5zG","children":[{"text":" return evaluateTree(root.left)||evaluateTree(root.right);"}]},{"type":"Paragraph","slateId":"hLvLq8paLbxq_NwAJbod0","children":[{"text":" }else { return e&&e"}]},{"type":"Paragraph","slateId":"DpjvPW5pZbHJ5q54u02f6","children":[{"text":"Q508出现次数最多的子树元素和"}]},{"type":"Paragraph","slateId":"h6tHzBm1N6UkgTZgQlQY4","children":[{"text":" //在main 是call dfsSum() 没有赋值给int "}]},{"type":"Paragraph","slateId":"DPjVpabq3tWNhVSlJP8do","children":[{"text":" // 但是需要 return int 因为dfs内部Recursion"}]},{"type":"Paragraph","slateId":"uxujWTZuC9m7zW17NSjE2","children":[{"text":" private int dfsSum(TreeNode root){"}]},{"type":"Paragraph","slateId":"4a8AqFQDoK5TGCWN3BJ_s","children":[{"text":" if(root==null)return 0;"}]},{"type":"Paragraph","slateId":"huBu3Xk3fO8rxKX0sq4ha","children":[{"text":""}]},{"type":"Paragraph","slateId":"qf_TOkGgLENgzjpj7aMBO","children":[{"text":" int summ=root.val + dfsSum(root.left)+dfsSum(root.right);// 循环每一棵树，直到它的leaf，然后再出来 mp put maxxCnt"}]},{"type":"Paragraph","slateId":"cqXtF7Nv-bGvDjqnbxfGG","children":[{"text":" mp.put(summ, mp.getOrDefault(summ,0)+1);"}]},{"type":"Paragraph","slateId":"BVY1NCRhFYv1C-_Ms4I3Z","children":[{"text":" maxxCnt = Math.max(maxxCnt, mp.get(summ));"}]},{"type":"Paragraph","slateId":"ZZtygv5OQXsO1lJIjiDE4","children":[{"text":" return summ;"}]},{"type":"Paragraph","slateId":"qj4bWGHAai6PA98SutLPn","children":[{"text":" "}]},{"type":"Paragraph","slateId":"2XnzWytoZNuPVyC6mKiPL","children":[{"text":"Q563二叉树坡度"}]},{"type":"Paragraph","slateId":"mwLUp1EvaTKpidlPiDNBx","children":[{"text":"int sumR = dfs(root.right); sumL=..."}]},{"type":"Paragraph","slateId":"lsvtE-MWyw170Vr3YEKZN","children":[{"text":" ans += Math.abs(sumL - sumR);"}]},{"type":"Paragraph","slateId":"bbUjlDPDwkwr2NhCbIltS","children":[{"text":" //先求 sum 再用已有的sum求坡度"}]},{"type":"Paragraph","slateId":"AyNwPtooRdk2pTEad0Emy","children":[{"text":" return sumL + umR + root.val; 归法计算，在Return 里写每个 dfs单位的计算法"}]},{"type":"Paragraph","slateId":"dDNn-U-MCEQaR1Aw7CZIg","children":[{"text":""}]},{"type":"Paragraph","slateId":"qKPAd5SwroktbHptXFwmu","children":[{"text":""}]},{"type":"Paragraph","slateId":"YHahKDOT691jfrnFga_u3","children":[{"text":"Q606 根据二叉树创建string"}]},{"type":"Paragraph","slateId":"iFQq0PgRdyWAJ2Qur1gxJ","children":[{"text":"Top down 做法，当做处理 root 和下面一行的 child node"}]},{"type":"Paragraph","slateId":"QS9b0CsOVtUnCgQ749ige","children":[{"text":"If(root==null)... return"}]},{"type":"Paragraph","slateId":"wBDkiJtUiCJu4E9SfH9xZ","children":[{"text":"ans.append(root.val)"}]},{"type":"Paragraph","slateId":"nzJPG8pBbqxo70ZRjFues","children":[{"text":"If(root.left ==null && r.right ==null) return;"}]},{"type":"Paragraph","slateId":"jYIk4bdHZIOPKzNzbheHc","children":[{"text":"ans.append ( \"(\" ） dfs(root.left); ans.append( \")\" );"}]},{"type":"Paragraph","slateId":"3UIWlo4UNAZWYVfEaWH69","children":[{"text":"if(rt. right!=null) ... .... ... same.. end."}]},{"type":"Paragraph","slateId":"75lD3uRu7aFIrcWmS48EP","children":[{"text":""}]},{"type":"Paragraph","slateId":"rkGyh77OHK0qBHVpmKmIT","children":[{"text":"Q2265统计值等于子树平均值的节点数"}]},{"type":"Paragraph","slateId":"Ki_l5mJJNgnRfGgk6fqmg","children":[{"text":" //cnt 遍历过的node数量, nodecurr。 int nodeCurr = cnt; cnt++;"}]},{"type":"Paragraph","slateId":"cc3AqwBnf9XJ_IeFjRJwH","children":[{"text":"// 假如不是null cnt++ dfs中 cnt变，等到两个dfs都结束 nodeCurr还是原来的 "}]},{"type":"Paragraph","slateId":"4VXhwy9Bh8TAkfNk4CP9g","children":[{"text":"//计算完上传ans 之后目前的child tree==值为totalsum 的一个节点所以末尾return totalSum"}]},{"type":"Paragraph","slateId":"qPXQQFUAZgrfFnRcx7nF2","children":[{"text":"Q1339 "}]},{"type":"Paragraph","slateId":"7D24uRmMeDl_zHNbmVJGj","children":[{"text":" private double dfs(TreeNode root){"}]},{"type":"Paragraph","slateId":"ErdhWoopjIbgAGm_s2sys","children":[{"text":" if (root==null)return 0;"}]},{"type":"Paragraph","slateId":"20RFks6mtsD5ug1zK0to4","children":[{"text":" double nodeSum=0; 这一行在里面写 == 在MAIN 外面写 double nodeSum；"}]},{"type":"Paragraph","slateId":"o6r5GWeG2xuT83QBdMMlH","children":[{"text":"虽然下一行计算，但是效果是一样的，"}]},{"type":"Paragraph","slateId":"epQhO2RLsUgCWYFMStIAZ","children":[{"text":" nodeSum = root.val + dfs(root.left)+dfs(root.right);"}]},{"type":"Paragraph","slateId":"EwkMl2u6nUdLKnO2gEggs","children":[{"text":"Q 1145 二叉树着色游戏两方着色比大小。 "}]},{"type":"Paragraph","slateId":"hUP6MbXPxTY6snzVhiejv","children":[{"text":"Q572 另一棵树的子树"}]},{"type":"Paragraph","slateId":"2r0BOK5D0KO7vlknUL569","children":[{"text":" public boolean isSubtree(TreeNode root, TreeNode subRoot) {"}]},{"type":"Paragraph","slateId":"1gjD60IdXInMzzornzXxD","children":[{"text":" if(root==null) return false;//无从寻找subtree 重合的内容"}]},{"type":"Paragraph","slateId":"G2XTTzFU4yAE9spWoTwcg","children":[{"text":" "}]},{"type":"Paragraph","slateId":"bM8pTWKMyrvu344P0l77J","children":[{"text":" return dfs(root,subRoot)||isSubtree(root.left, subRoot)|| isSubtree(root.right, subRoot);// 这里是巡遍元树，找顶点和subtree root重合顶点左右是否重合到下面的node DFS按照普通两树重合写"}]},{"type":"Paragraph","slateId":"K2_SiJjvv7_jMdJK1DTmE","children":[{"text":""}]},{"type":"Paragraph","slateId":"XuVWGwECamK3skfSpE7u0","children":[{"text":"§2.4 自底向上 DFS：删点剪枝（重点操作可以节省时间空间）"}]},{"type":"Paragraph","slateId":"NyZz7lXNkqOI_ppyZkvv-","children":[{"text":"Q814. 二叉树剪枝"}]},{"type":"Paragraph","slateId":"w2AkPABVqBi40pgwX2g9V","children":[{"text":"TreeNode function()"}]},{"type":"Paragraph","slateId":"rsDGuspy1r-nloc-TU6xr","children":[{"text":"当遍历每个节点时，等于更改自身的节点 root.left = dfs( 有 = 直接在原树上替换"}]},{"type":"Paragraph","slateId":"jqo5ghDipRi1QZrJXBcrs","children":[{"text":" "}]},{"type":"Paragraph","slateId":"eSellzlv0ETbxLK_ED7Ao","children":[{"text":" if(root.left==null &&root.right==null &&root.val ==0) return null;//将特定的末尾Leaf =1 节点替换为null "}]},{"type":"Paragraph","slateId":"3KlNbH7H4Bz5lgctrDmho","children":[{"text":""}]},{"type":"Paragraph","slateId":"JMBH4tTGURBfw8FbZ9ePT","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"CePNol-QwM1i-l5lTiGiq","children":[{"text":"return root / return null"}]},{"type":"Paragraph","slateId":"Y9D79S-C9TTQGXIa_ek_j","children":[{"text":"前者不变后者把它清空"}]},{"type":"Paragraph","slateId":"bm1YnkJvIVpDv3vXmFRin","children":[{"text":""}]},{"type":"Paragraph","slateId":"HcU3iqZAnFi1URAs9ia2M","children":[{"text":"Q1325. 删除给定值的叶子节点假如删除叶子之后，特定值节点也成了叶子（并非上面）也删除。类似上面题目"}]},{"type":"Paragraph","slateId":"6_eLz0frIFgvYSqZA3t42","children":[{"text":"Q1110 删点成林"}]},{"type":"Paragraph","slateId":"p07nDqBJrvGDoe0yrHukD","children":[{"text":" if(!del.contains(root.val)) ans.add(root);//重点1 最后查一下top root一个有没有在recursion加入由于下面加的都是子树"}]},{"type":"Paragraph","slateId":"KvuEPJ0jkPlshTm5V8MVh","children":[{"text":"in DFS: ...... r. left=dfs r. right=dfs"}]},{"type":"Paragraph","slateId":"RYjJ5ei6uk9-Ek9886ni1","children":[{"text":" if(del.contains(root.val)){"}]},{"type":"Paragraph","slateId":"ExWkMeMP0W0QjUgRvF24t","children":[{"text":" if(root.left!=null){//重点2"}]},{"type":"Paragraph","slateId":"PVzRaEKy-1iE92aYlyyhw","children":[{"text":" ans.add(root.left);//2"}]},{"type":"Paragraph","slateId":"X1HIqYO91xif8eD9sAEut","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"mB7KX3xy_YlyO6hX6WlJ5","children":[{"text":" if(root.right!=null){//这些操作才是不同于前两题剪枝的不是清空而是加入散落的sub tree node。"}]},{"type":"Paragraph","slateId":"OasEYOCjM7FIx6dKlKmUJ","children":[{"text":" ans.add(root.right);//"}]},{"type":"Paragraph","slateId":"ZBRrXH9vTZyYTll8yjUKm","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"oAVy43TkrT5F04jTehumj","children":[{"text":" root=null;"}]},{"type":"Paragraph","slateId":"_MUdZn-tFFmwBND1hNd1U","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"rxoZKhkuxALm1sVU5FBwZ","children":[{"text":" //只需要这个.因leaf不是关键，关键是去除特定value的node"}]},{"type":"Paragraph","slateId":"G9kKDlEu6KukxJFCbECi9","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"sUoIuLzEDZPzatTdvDvCZ","children":[{"text":""}]},{"type":"Paragraph","slateId":"M4wp3pME5bvIO5vNN3wxk","children":[{"text":"Q 538. 把二叉搜索树转换为累加树 "}]},{"type":"Paragraph","slateId":"lMFUv__KMEYzlmRTcmVOq","children":[{"text":" dfs(root.right);"}]},{"type":"Paragraph","slateId":"ibfRSvS5dD0rIUZDv7QBG","children":[{"text":" //in binary search tree //all root.right.val >root "}]},{"type":"Paragraph","slateId":"VyiD0kRwaiJfAhwYmQFJX","children":[{"text":" s+=root.val;"}]},{"type":"Paragraph","slateId":"bSB1EnnfDhSndV6NiA4E5","children":[{"text":" root.val=s;//key"}]},{"type":"Paragraph","slateId":"mR516ZNov5UcSJ9uZL7SP","children":[{"text":" dfs(root.left);"}]},{"type":"Paragraph","slateId":"QNizfWkzeALdmZJITBvjH","children":[{"text":" if(leftMaxD==rightMaxD &&leftMaxD==maxD){"}]},{"type":"Paragraph","slateId":"gNAB_KyDvVv6Z_iQeuaXv","children":[{"text":" ans=root;//此对应是，在Dfs的某一个recursion 中的某一个Root 假如最左边的leaf和最右边的leaf都是 deepest,则原本的最顶处根就是ans"}]},{"type":"Paragraph","slateId":"LLWCaoO67lQdSFkF5GLoA","children":[{"text":""}]},{"type":"Paragraph","slateId":"_GU9YnNaUbPng3HhyrCdt","children":[{"text":" "}]},{"type":"Paragraph","slateId":"dWSrpLSHgPV-9T8dl4_ML","children":[{"text":""}]},{"type":"Paragraph","slateId":"bemynVGfBZ3Xx51D21hcE","children":[{"text":"其实就是把所有的数字从大到小排，然后按照bst 的定律，从最右下开始，逐个安排成node 值，到左边"}]},{"type":"Paragraph","slateId":"dIfFtX8ex03HnFe32czi8","children":[{"text":"重点 1. sum 在 dfs 外设定"}]},{"type":"Paragraph","slateId":"fzXSL99SbtSDL8n8eQcAz","children":[{"text":"s+=root.val;"}]},{"type":"Paragraph","slateId":"8Y4ev7kyaR_p6hcY_w896","children":[{"text":""}]},{"type":"Paragraph","slateId":"tZsyFXanqeGI14rLoDL6j","children":[{"text":"Q865 具有所有最深节点的最小子树"}]},{"type":"Paragraph","slateId":"qzjabRUeV_WTb75UTSgk0","children":[{"text":" if(root==null){//到了每个叶子的末尾都要更新max depth以便于其他追踪"}]},{"type":"Paragraph","slateId":"kbYAzHKgI_6KaAYEkyjP3","children":[{"text":""}]},{"type":"Paragraph","slateId":"Ijiu3yXvu0whIP9bb84cL","children":[{"text":"int rightMaxD = dfs(root.right,depth+1);"}]},{"type":"Paragraph","slateId":"eSF18e9UP6gJDxlGGyB5_","children":[{"text":" "}]},{"type":"Paragraph","slateId":"BGJ2a-YTx6M-GWfoJzRvm","children":[{"text":" if(leftMaxD == rightMaxD && leftMaxD == maxD){"}]},{"type":"Paragraph","slateId":"G7F3iDD3ZWFzbW2wK_r-p","children":[{"text":" ans = root;//此对应是，在Dfs的某一个recursion 中的某一个Root 假如最左边的leaf和最右边的leaf都是 deepest,则原本的最顶处根就是ans"}]},{"type":"Paragraph","slateId":"rgrTeB-lYvf3YrH9S-Y0l","children":[{"text":" } //find all parent nodes for the deepest leaf nodes."}]},{"type":"Paragraph","slateId":"aB01M8U1vJZZE7ViW6oNy","children":[{"text":" return Math.max(leftMaxD,rightMaxD);"}]},{"type":"Paragraph","slateId":"tAUVmTpZ8L3eqFglhIx1V","children":[{"text":""}]},{"type":"Paragraph","slateId":"hMMX1AQ69C8CxoeismVsk","children":[{"text":"Q1080根到叶路径上的不足节点 //对于非叶节点假如删除后还余下一个child 到leaf路线，则此node还有用，。"}]},{"type":"Paragraph","slateId":"bhPyBHZUfmAVGNF2VtMVA","children":[{"text":"by灵茶山大神： “ 如果 node 的儿子都被删除，说明经过 node 的所有儿子的路径和都小于 limit，这等价于经过 node 的所有路径和都小于 limit，所以 node 需要被删除。” "}]},{"type":"Paragraph","slateId":"3m7rAe5Nmlzv2ZwO_95kb","children":[{"text":"DFS"}]},{"type":"Paragraph","slateId":"v3IZoX7yU7SLEwEt8qjiA","children":[{"text":"if(node==null) return null;"}]},{"type":"Paragraph","slateId":"Nn-kGvuWIwc1wOfFsxp55","children":[{"text":" if(node.left == null && node.right==null){// LEAF节点"}]},{"type":"Paragraph","slateId":"BX8KL1BOnrcdXNdtFnjgL","children":[{"text":" if(node.val ans){"}]},{"type":"Paragraph","slateId":"ce4-b5IAblNzkOB1v__6t","children":[{"text":" if(root==null) return;"}]},{"type":"Paragraph","slateId":"oUJ9bXNsiMjNq2PJIC2C7","children":[{"text":" "}]},{"type":"Paragraph","slateId":"XUebKirIcOIXBTaOzz_Ot","children":[{"text":" StringBuilder pathSB = new StringBuilder(pathPrev);//activate prev record path unfinished"}]},{"type":"Paragraph","slateId":"Tp1g9P3TXXEwL2MZ3qwLa","children":[{"text":" pathSB.append(root.val); // 单一态单位为一个node 的操作"}]},{"type":"Paragraph","slateId":"ekYArqQolKvbevhnzTIXU","children":[{"text":""}]},{"type":"Paragraph","slateId":"2LAjfyiG0csFB0zkJEyWI","children":[{"text":" if(root.left==null &&root.right==null){//叠加态， left right 的操作"}]},{"type":"Paragraph","slateId":"wAcgDSIDtlFBYkY091iX2","children":[{"text":" ans.add(pathSB.toString()); // 为leaf 不为 leaf"}]},{"type":"Paragraph","slateId":"XogdSUy0HRIP8mma4Emm8","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"cLkWErUuXBlzdtU42p7-H","children":[{"text":" pathSB.append(\"->\");"}]},{"type":"Paragraph","slateId":"FopeEeO2NwiF803MFM_jv","children":[{"text":" dfs(root.left, pathSB.toString(), ans);dfs(root.right, pathSB.toString(), ans);"}]},{"type":"Paragraph","slateId":"8JzEHxOZkJlLWgFKZXtt2","children":[{"text":"Q 113 路径总和找到总和==target的路径，并记录做法类似上题，但是加上"}]},{"type":"Paragraph","slateId":"FH-uvl7jZK10ILI__Uzjm","children":[{"text":" path.remove(path.size()-1);//clear the earliest entry node in working space（ path是记录路径的list,会被add进ans）"}]},{"type":"Paragraph","slateId":"pXXK_zZXre95MAE9IUDlm","children":[{"text":"回溯污染问题，为什么最后要删除path entry最后一个节点而上一题不需要？"}]},{"type":"Paragraph","slateId":"Tk12YNB-e9QL5EJpMkiDT","children":[{"text":"因为到新的branch 会容易带着旧数据，污染next path entry 所以结尾清理"}]},{"type":"Paragraph","slateId":"1R5optT39jfziF7H_CjPm","children":[{"text":"https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247487910&idx=1&sn=2670aec7139c6b98e83ff66114ac1cf7&chksm=fb418286cc360b90741ed54fecd62fd45571b2caba3e41473a7ea0934f918d4b31537689c664&scene=21#wechat_redirect"}]},{"type":"Paragraph","slateId":"-uS5utgFTfzNTFXHsUeiA","children":[{"text":""}]},{"type":"Paragraph","slateId":"1CoTwzevVmPPqmxxc9VeY","children":[{"text":"Q1457 二叉树中的伪回文路径 "}]},{"type":"Paragraph","slateId":"VIUTE_0uc38aR6sx5Ztj7","children":[{"text":"cnt[root.val]++; int ans=0;"}]},{"type":"Paragraph","slateId":"L6hVsiDEknGDlxr_OoVro","children":[{"text":"if(root.right==null && root.left==null){"}]},{"type":"Paragraph","slateId":"81zgEgw_GUBYwkpyOlN_5","children":[{"text":" if(isPseudoP(cnt)){"}]},{"type":"Paragraph","slateId":"hSakCpWzH2AhN76vYqUtc","children":[{"text":" ans=1;//这个1 不会是最终答案，因为在往上的过程中，dfs+ dfs只会把所有的答案加起来。"}]},{"type":"Paragraph","slateId":"DoUy65W54iDa3IWf2Vr4T","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"CskOn_r71mhThHoC3TDx8","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"UFJnKcGlFvTGakrY_F507","children":[{"text":" ans = dfs(root.left, cnt)+ dfs(root.right, cnt);"}]},{"type":"Paragraph","slateId":"fLlz07PEz1OcUmGNbTDw4","children":[{"text":"}"}]},{"type":"Paragraph","slateId":"mMgsRaz-sDStzQplE2ZWg","children":[{"text":" cnt[root.val]--;//到其他的node branch当前node已遍历完"}]},{"type":"Paragraph","slateId":"Lh__wcdxAo8W6qjWBQrlI","children":[{"text":" return ans; 假如ans 是1 Return 1 假如root = null return 0 "}]},{"type":"Paragraph","slateId":"wR3YSZWKhoACigca1BwbI","children":[{"text":"boolean isPseudoP(int[] cnt){也值得一看（都是偶数量的数字，假如有奇数，只可能是palindr中间那个，所以遍历cnt[x] oddSum = x%2的总和为 <=1 ）"}]},{"type":"Paragraph","slateId":"-CCvvMPzhtZP2sL0gHkfZ","children":[{"text":""}]},{"type":"Paragraph","slateId":"nBEIel6XGGpyjSZhfkccv","children":[{"text":"Q437路径总和 III"}]},{"type":"Paragraph","slateId":"DSI7WkYlxL-sGIaOoomiW","children":[{"text":" int cntPath= ans.getOrDefault(currSum-target,0);//但凡有一个非零的值，满足任何的currSum , -target, 则这个值就是现下收集到的target的路径数前缀法"}]},{"type":"Paragraph","slateId":"SXRQLgbj7jeOhinmngtah","children":[{"text":""}]},{"type":"Paragraph","slateId":"YeKv9oG6dywDCuzZ2p5f7","children":[{"text":"Q235. 二叉搜索树BST的最近公共祖先"}]},{"type":"Paragraph","slateId":"rAQJ0PNJ_VUOEakIiMc5k","children":[{"text":" public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {"}]},{"type":"Paragraph","slateId":"MpCDg_iZ-2wpNtwY857ss","children":[{"text":"// 运用BST特性，eg 3, 9 in [6,2,8,0,4,7,9,null,null,3,5] 6 是3 9 之间，则根据特性6必须是答案。同理 0 5的答案是2 6>5 6.left=2"}]},{"type":"Paragraph","slateId":"LYlcq3SRvzIhUFFf14IR7","children":[{"text":" while(root!=null){"}]},{"type":"Paragraph","slateId":"HEDSfCdSzvpWkzOFyTnx8","children":[{"text":" if(root.valp.val &&root.val>q.val)root=root.left;"}]},{"type":"Paragraph","slateId":"VmCpyvjap2aGcnjctVgGA","children":[{"text":" else break;"}]},{"type":"Paragraph","slateId":"T3N375OheQ7KkVezheBFe","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"v0wvcSBKTbOAk_m-vlfUM","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"ReCK1PxkG1-IbMGRbWsei","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"FbhhPM3cJbMWb43XVjtr_","children":[{"text":"Q 236 二叉树的最近公共祖先靠背住"}]},{"type":"Paragraph","slateId":"szX26mZhHZIYjsDN3rDMQ","children":[{"text":" public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {"}]},{"type":"Paragraph","slateId":"voCWwYR81_CLQ3lATNcbQ","children":[{"text":" if(root==null||root==p||root==q){"}]},{"type":"Paragraph","slateId":"e2IeQUUKBrS8cPWWN-mqr","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"a066XuWZD8km08s6fakCy","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"7GbA2xN6Hb2aGhnqpjNlJ","children":[{"text":" TreeNode left= lowestCommonAncestor(root.left,p,q);"}]},{"type":"Paragraph","slateId":"yqwC2sT0gwG-xINcCEQYt","children":[{"text":" TreeNode ri= lowestCommonAncestor(root.right, p,q); "}]},{"type":"Paragraph","slateId":"6byUH7EbXHescCA1ViC8x","children":[{"text":" if(left!=null && ri!=null){//左右都找到 pq"}]},{"type":"Paragraph","slateId":"xsgI0AZFMzs_47BhzUY9_","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"n5EqWrtqHAJ4yItcecfCF","children":[{"text":" }else if(left!=null){ //说明都在左子树"}]},{"type":"Paragraph","slateId":"wRnCCqVuOazr2Qw6NyxNz","children":[{"text":" return left;"}]},{"type":"Paragraph","slateId":"Tx-rzhG-KxYPfxilgh1nB","children":[{"text":" } else{"}]},{"type":"Paragraph","slateId":"5WnDafQTM4iwqjnFTfqht","children":[{"text":" return ri; //此时都在right里或者在当前 //Recursion 里都没有 null 需要回上个node"}]},{"type":"Paragraph","slateId":"NB07LOqt4Yq-cQdSF7H-Y","children":[{"text":"§2.9 二叉搜索树BST 专题"}]},{"type":"Paragraph","slateId":"Tkak2TbJPEJdQsW6c_nm9","children":[{"text":"Q700. 二叉搜索树中的搜索和 Q235 一样，目前值大了搜左，小了搜右边"}]},{"type":"Paragraph","slateId":"g7ouPw-oHUCEbz3-K6XKd","children":[{"text":""}]},{"type":"Paragraph","slateId":"RDgqv80WIwrzhJZ0_RPAN","children":[{"text":"Q530. 二叉搜索树的最小绝对差 int minD = Integer.MAX_VALUE;"}]},{"type":"Paragraph","slateId":"Z6BQS3xgltKy6rB7cohao","children":[{"text":" int preval = Integer.MIN_VALUE/2;//注意避免overflow. root val 0-10^5"}]},{"type":"Paragraph","slateId":"hFTJwmFobB5MxTxPrLsdy","children":[{"text":" public int getMinimumDifference(TreeNode root) {"}]},{"type":"Paragraph","slateId":"KMDpb4s2USrnB8SBZfYmj","children":[{"text":" dfsDiff(root);"}]},{"type":"Paragraph","slateId":"mB-_pvamOK_340JVN-IZz","children":[{"text":" return minD;"}]},{"type":"Paragraph","slateId":"NWzYis0bigY1EEg2EvHaY","children":[{"text":" private void dfsDiff(TreeNode root) {"}]},{"type":"Paragraph","slateId":"7iKT7JjJ0kQ0oqJlGLrLR","children":[{"text":" if(root==null ) return;"}]},{"type":"Paragraph","slateId":"WySpS3RToepGA_POqLF6Q","children":[{"text":""}]},{"type":"Paragraph","slateId":"rSA1du-iSNj3yamc6NcK2","children":[{"text":" dfsDiff(root.left);"}]},{"type":"Paragraph","slateId":"ZMl7kujG-QN-RBPg38kim","children":[{"text":" minD = Math.min(minD, root.val-preval);"}]},{"type":"Paragraph","slateId":"KPVgbeCCCcGeIFsqp1CDV","children":[{"text":" preval = root.val;//先搜左再右边，所以不需要 math abs ， preval始终小于rootV"}]},{"type":"Paragraph","slateId":"Xemz9GC9JtyCFR5e-r2Di","children":[{"text":" dfsDiff(root.right);"}]},{"type":"Paragraph","slateId":"bItqtHiTyXHwaULUq2-RG","children":[{"text":"Q938. 二叉搜索树的范围和 "}]},{"type":"Paragraph","slateId":"AZJI8hG4cFDK_gmLzoRLf","children":[{"text":"通用模板：前 if(root=null) return 后 dfs(root.left) dfs(root.right)"}]},{"type":"Paragraph","slateId":"LIp0vFZz9n2N9ezvGXuiX","children":[{"text":"if(root.val>=l &&root.val<=h){//加上这段在中间"}]},{"type":"Paragraph","slateId":"VfpvYGKCa1X7lEoblzShJ","children":[{"text":" sum+= root.val;"}]},{"type":"Paragraph","slateId":"Pj5Y8Th6t_6WXsZEDGMcF","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"U5d0TskdxMjxv4GSwIpIh","children":[{"text":"Q 501 二叉搜索树的众数注意 dfs在这里分开 dfs left-->update-> dfs right"}]},{"type":"Paragraph","slateId":"A1my3nmNxF1fX_Fdf7ksg","children":[{"text":" inOrder(root.left);//dfs left要在这里，为什么。？为什么前两题不需要呢"}]},{"type":"Paragraph","slateId":"RLKGwdsVe105QTjXaOYrt","children":[{"text":" // left right 分开因为此题需要绝对的递增才能最大化节省空间时间，所以利用原理。？因为keep track of pre, pre需要单调递增才能算mode"}]},{"type":"Paragraph","slateId":"QMSRFOKeOq4zle2XUIkz0","children":[{"text":" if(pre!=null &&root.val==pre){ update the data"}]},{"type":"Paragraph","slateId":"zBf7kp3Tr7fVU5oCOpRd7","children":[{"text":" currCnt++;"}]},{"type":"Paragraph","slateId":"UgxtoZo_JByD5fMz8P7zr","children":[{"text":" }else currCnt=1;"}]},{"type":"Paragraph","slateId":"06fqCE2lumZgIYRuGHmal","children":[{"text":" if(currCnt>maxCnt){"}]},{"type":"Paragraph","slateId":"dS3RIVyR09g3rvDZ8rzCD","children":[{"text":" maxCnt = currCnt; arrCnt=1;"}]},{"type":"Paragraph","slateId":"8kgqx-1IgkhATH5YSTUOW","children":[{"text":" }else if(currCnt==maxCnt){//这个else if 是为了第二次call 填写array"}]},{"type":"Paragraph","slateId":"lGFMNBMtG5jMBF5WzdegM","children":[{"text":" if(modeArr!=null)//第二次"}]},{"type":"Paragraph","slateId":"QjasnRDZA48MAgHuGywOz","children":[{"text":" modeArr[arrCnt] = root.val;"}]},{"type":"Paragraph","slateId":"nZK0JQsGf0GGNZuTz14pj","children":[{"text":""}]},{"type":"Paragraph","slateId":"7LOUzpN2DxuLQQe2JWkRu","children":[{"text":" arrCnt++;//第一次"}]},{"type":"Paragraph","slateId":"mC2v8g_tqeHfbymlWjg2K","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"K9HSdQxtqt5fUh0W7YwJG","children":[{"text":" pre = root.val; inOrder(root.right);"}]},{"type":"Paragraph","slateId":"N880yYWK7-DY_A935NjHt","children":[{"text":"Q 230二叉搜索树中第 K 小的元素"}]},{"type":"Paragraph","slateId":"p4VWmn4hrWYeWQuPcFXmY","children":[{"text":" \t\t\tdfs(root.left);"}]},{"type":"Paragraph","slateId":"4T00eWHui7F7opWlN2GKy","children":[{"text":" if(--kRem==0){ //不是当前k=0,是k先--，然后check. 假如krem =1 root would be ans"}]},{"type":"Paragraph","slateId":"-g1zNBW6BLT-N2JpPi7Ow","children":[{"text":" ans = root.val;}"}]},{"type":"Paragraph","slateId":"TInff-jb9bAdNODKBhXbg","children":[{"text":" dfs(root.right);"}]},{"type":"Paragraph","slateId":"fjInpB7fSJX6aDPQOdE1h","children":[{"text":"Q 98 验证是否BST"}]},{"type":"Paragraph","slateId":"bD7Cei5MZ2YUIWZp1zIu6","children":[{"text":" if(root==null) return true;//注意这个到末尾搜索完毕并且没有被阻拦所以"}]},{"type":"Paragraph","slateId":"FilDiTb7rup1Aofq84C5o","children":[{"text":" int x = root.val;//第一个（）暗含false true判断"}]},{"type":"Paragraph","slateId":"kJANIrFzA_4uwqS7gzgt0","children":[{"text":" return ( x > lBound && x< rBound )&& dfs(root.left,lBound,x)&&dfs(root.right,x,rBound);"}]},{"type":"Paragraph","slateId":"s_K-Iwlw-t6vrGpIQA6m0","children":[{"text":"Q 1305 两棵二叉搜索树中的所有元素可以多做此题想着分开做"}]},{"type":"Paragraph","slateId":"＊＊＊0ZhCpFTJWktpNHYlHH","children":[{"text":"1 pointer 的设置"}]},{"type":"Paragraph","slateId":"bGCQ_59rfHo-TpOlRa_oc","children":[{"text":"2 ans.addAll ( li2. subList ( p2, li2 . size() )); 两个list 的Function addAll.加入全部元素。 subList: [ index end)"}]},{"type":"Paragraph","slateId":"1C6-iwyaPjkRnLLK8-Ehr","children":[{"text":"按升序dfs 把BST 转换为List dfs(r1.left,ans) ans.add(r1.val); dfs(r1.right,ans);"}]},{"type":"Paragraph","slateId":"lz8YnP-GLatJfP＊＊＊sJDZ","children":[{"text":""}]},{"type":"Paragraph","slateId":"W_-fBAGr9hekC50e2WbEt","children":[{"text":"Q99 恢复BST"}]},{"type":"Paragraph","slateId":"xI7mTy4xp5G8-QRKDCIwN","children":[{"text":" DFS LEFT) if(pre==null){"}]},{"type":"Paragraph","slateId":"bGlvkHXTt-LgUd2LUHWQo","children":[{"text":" \t\t\t pre=root;"}]},{"type":"Paragraph","slateId":"zlTJaAUVCh7i9cPHqTYrv","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"CfARvJMMldY30BAY8_EAD","children":[{"text":" if(pre.val > root.val){//每一个pre < curr root是正常顺序"}]},{"type":"Paragraph","slateId":"8fdmVh8C5UEYquXtI8Pcq","children":[{"text":" firstLg = root;// 排序中调换，一定后大先小。所以 large=root small = pre small是已经过去的那个"}]},{"type":"Paragraph","slateId":"JPrDS6rlAH5koYO2TDGCg","children":[{"text":" if(lastSml==null) lastSml = pre;"}]},{"type":"Paragraph","slateId":"y06-RKJNOgJRcVOAsxFHa","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"2-kXaxKdFO003g3b6xhqN","children":[{"text":" pre=root; }"}]},{"type":"Paragraph","slateId":"8qnYWQoPsY6Nh-aS5Gy1C","children":[{"text":" dfs(root.right);"}]},{"type":"Paragraph","slateId":"u4AeIdYnOI63luokjJ0Ss","children":[{"text":"Q897. 递增顺序搜索树用dummyH . curr=dummy head. curr.right = new TreeNode(i). curr=curr.right"}]},{"type":"Paragraph","slateId":"XpX92jWMaMOE_jjvXwmEx","children":[{"text":"Q 2476 没说平衡的BST，假如一个subtree过大。所以需要重新排序，中序遍历，近数组。再用二分法"}]},{"type":"Paragraph","slateId":"kGrZyUoMTYfg5G4BRvLK1","children":[{"text":"二分法复习：能取得大于target 的最小值"}]},{"type":"Paragraph","slateId":"1rkNx1S6LhB_Y0rC6c-Qx","children":[{"text":" int low = 0, high = arr.size();"}]},{"type":"Paragraph","slateId":"yAW8CJLh_pR3fhalxRE5V","children":[{"text":" while(low=target){"}]},{"type":"Paragraph","slateId":"HWk5ChkNSfYjQPxMBIYeI","children":[{"text":" high = m;"}]},{"type":"Paragraph","slateId":"kqV5x0yThGc374-p9FZm9","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"2S3Rb2G9JIn5_9EYQu4U1","children":[{"text":" low = m+1;"}]},{"type":"Paragraph","slateId":"5BxSQZzJDW75tguU5JlJG","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"dcwHfhxnnjXYDVi-CPhAN","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"tVO0qOfLLeYanBJxMsfcW","children":[{"text":" return low;"}]},{"type":"Paragraph","slateId":"ed0zsmWETO8iKVQ77UFya","children":[{"text":"Q653 两数之和 IV 朴素求数字==sum k 的题， "}]},{"type":"Paragraph","slateId":"j_ut4drvbDp_JEHxKmVZa","children":[{"text":"§2.10 创建二叉树"}]},{"type":"Paragraph","slateId":"RFWSZaFjz_K0XqyOJ9qR2","children":[{"text":"Q108将有序数组转换为二叉搜索树"}]},{"type":"Paragraph","slateId":"njB3KEGeRVFJdhA-df8dh","children":[{"text":" public TreeNode helper(int[] nums, int left, int right){"}]},{"type":"Paragraph","slateId":"jBjoDp4DsYj55GUPRZaGg","children":[{"text":" if(left>right){ // 二分法转换成填数组方式"}]},{"type":"Paragraph","slateId":"QIMo-PGDG-vXV07bsDJ3V","children":[{"text":" return null;"}]},{"type":"Paragraph","slateId":"tluMv8Xu19y4BjKBROS5J","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"MGDysfXHcJx7xy8ZB6TK8","children":[{"text":" int mid = (left+right)/2;"}]},{"type":"Paragraph","slateId":"nV_dg_4A1dgF4HLykuWSg","children":[{"text":" TreeNode root = new TreeNode(nums[mid]);"}]},{"type":"Paragraph","slateId":"R2WMvu8hKyzGsl0DidiAi","children":[{"text":" root.right = helper(nums,mid+1,right);"}]},{"type":"Paragraph","slateId":"gyefj283z0QB6cFpdJhum","children":[{"text":" root.left = helper(nums,left,mid-1);"}]},{"type":"Paragraph","slateId":"GUeKmmn0a07hVgxEJTtg7","children":[{"text":" return root;"}]},{"type":"Paragraph","slateId":"YRly1U39jI9RBRX3zlrPe","children":[{"text":"Q654. 最大二叉树类似"}]},{"type":"Paragraph","slateId":"ff_-K1xIDZpeF9Z_1Rxkz","children":[{"text":"Q1008 前序遍历构造 Q 1382将二叉搜索树变平衡 Q2196. 根据描述创建二叉树挺重要的题，多看"}]},{"type":"Paragraph","slateId":"13IDgiPUeE_6o4pffrex9","children":[{"text":"Q105. 从前序与中序遍历序列构造二叉树 Q106 889难题多复习"}]},{"type":"Paragraph","slateId":"P2J5kdCvJAbA4MHW-a1V0","children":[{"text":"Q669. 修剪二叉搜索树保留LOW HIGH范围内，其他剪枝不改变结构"}]},{"type":"Paragraph","slateId":"CN5qlPaBQSxoA34WZce-G","children":[{"text":"public TreeNode trimBST(TreeNode root, int low, int high)"}]},{"type":"Paragraph","slateId":"MKMLwas9BfiNrJvPB4Osh","children":[{"text":" if(root.val root=root.left"}]},{"type":"Paragraph","slateId":"lgzY-KyV4EQJ4uobvkpjD","children":[{"text":" "}]},{"type":"Paragraph","slateId":"fj4Z-gUBuxUaCg54fgFho","children":[{"text":" }else{"}]},{"type":"Paragraph","slateId":"DyY6RSoiVpxitID3gvudW","children":[{"text":" TreeNode successor = root.right;"}]},{"type":"Paragraph","slateId":"jjH2v_PsruEZV7YSerZ1F","children":[{"text":" while (successor.left != null) {"}]},{"type":"Paragraph","slateId":"gxPiG3csT5a3DJK-ebZDz","children":[{"text":" successor = successor.left;"}]},{"type":"Paragraph","slateId":"rkuqjdnWpHTIpr9DaNDXY","children":[{"text":" }"}]},{"type":"Paragraph","slateId":"GpbiC7iBQqgxh6ZbsN4XK","children":[{"text":" ////右子树的最小最左子树，为替代Root"}]},{"type":"Paragraph","slateId":"A2HhoX3g7XVEKIGxMnU-c","children":[{"text":" root.right = deleteNode(root.right, successor.val);"}]},{"type":"Paragraph","slateId":"JY-XOZvXCSULqsfCnZujk","children":[{"text":" successor.right = root.right;"}]},{"type":"Paragraph","slateId":"ncXPDqyAHN6B0AxSEtSUU","children":[{"text":" successor.left = root.left;"}]},{"type":"Paragraph","slateId":"AAco0YJCDmcNaJdiOfz1B","children":[{"text":" return successor;"}]},{"type":"Paragraph","slateId":"scaRZ-YaoO-NPensLquN7","children":[{"text":" } "}]},{"type":"Paragraph","slateId":"8GADe9p_c4SJ5I8iE_Gcw","children":[{"text":" if(root.val