负基础入门leetcode二叉树相关题解+思路（二）

在这种政治中心

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由在这种政治中心于 2020-6-18 23:07 编辑

时隔n天……来填坑啦！

刷题，就得按照专题刷。笔者本人也只是一个初学者，在刷题的过程之中深深感到了“套路”的重要性，在此做一些总结和摘抄，希望可以帮到更多和我一样的”负基础”同学们。若有大佬不吝赐教，本人十分感激。

顺带希望各位觉得有帮助可以加一下米，想看面经的米总是不够，谢谢各位！

推广一下个人博客，https://timzhouyes.github.io/

二叉树，其构成为一个根节点，且必定有两个子节点。在最下面的叶子层全都是为空的子节点。

那么每次以其左子树和右子树作为操作单位，就很自然的将整个树拆分成了更小的树，并且可以结合最后的叶子节点层全都是Null来进行递归的结束判定，可以说树这个结构是天然适合递归的。

参考：https://github.com/CyC2018/CS-No ... %20-%20%E6%A0%91.md

在大佬的基础之上将一些题目的解法做了更简化的扩展，有些题目的解法，大佬将很多步骤缩成一步，太过简练，我在此将其进行扩展发散，尽量每一步只做一个操作，让大家看的更清楚一些。

面向大佬警告：不是时间最优，不是效率最优，只是便于理解的代码版本，请各位大佬高抬贵手……

打*的是笔者自己做不出来的题目，标记好来再次刷。打&的是最好再回顾一次的题目。
根据前中/中后/前后遍历顺序还原二叉树

20. 从前序和中序还原二叉树

105 Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

这种还原二叉树的题目，本质上都是一样的：每次找到根节点是谁，左边子树在对应的序之中是从哪到哪，然后递归即可。每次返回的都只是根节点这个新建节点。

步骤为：

找到对应的根节点A，前序的话第一个节点一定是根节点
找到左右子树两部分：在中序遍历之中A的左边一定是左子树，右边一定是右子树。
递归求解即可。

注意：此处在开始要判断两个数组的长度是否一致/长度是否为0。满足的话直接返回null就好了。至于其中的copyOfRange()为什么可以取下标是1，是因为代码之中写了这个注释：

* @throws ArrayIndexOutOfBoundsException if {@code from < 0}
* or {@code from > original.length}

复制代码

可见如果一个数组的长度为1，那么是可以执行类似copyOfRange(array,1,1)这样的代码的，其返回值会是一个空的array。

将代码做出改进，发现三种还原之中，如果都对当前数组长度为1的时候进行一个判断并且直接返回值，可能要更好一点。下面的代码也都是加入了相应的判断。

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given
preorder = [3,9,20,15,7]

inorder = [9,3,15,20,7]
复制代码
Return the following binary tree:
3

/ \

9 20

/ \

15 7
复制代码

class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length!=inorder.length || preorder.length==0) return null;
int head = preorder[0];
int position = findPosition(inorder,head);
TreeNode node = new TreeNode(head);
if(preorder.length==1) return node;
node.left=buildTree(Arrays.copyOfRange(preorder,1,position+1),Arrays.copyOfRange(inorder,0,position));
node.right = buildTree(Arrays.copyOfRange(preorder, position+1,preorder.length),Arrays.copyOfRange(inorder,position+1,inorder.length));
return node;
}
public int findPosition(int[] array, int num){
for(int i=0;i<array.length;i++){
if(array[i]==num) return i;
}
return -1;
}
}

复制代码

21. 从中序和后序还原二叉树

106 Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

本题和上一个题目几乎全部相同。只是在递归的时候注意一下两个部分的起始点即可。

class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0|| inorder.length!=postorder.length) return null;
TreeNode node = new TreeNode(postorder[postorder.length-1]);
int i=0;
if(inorder.length==1) return node;
for(int j=0;j<inorder.length;j++){
if(inorder[j]==postorder[postorder.length-1]) i=j;
}
node.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
node.right = buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),Arrays.copyOfRange(postorder,i,postorder.length-1));
return node;
}
}

复制代码

22. 从前序和后序还原二叉树

889 Construct Binary Tree from Preorder and Postorder Traversal

思路一样，就不赘述了。

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
if(pre.length!=post.length || pre.length==0) return null;
TreeNode root = new TreeNode(post[post.length-1]);
int index = 0;
if(pre.length==1) return root;
for(int i=0;i<post.length;i++){
if(post[i]==pre[1]) index = i;
}
root.left = constructFromPrePost(Arrays.copyOfRange(pre,1,index+2),Arrays.copyOfRange(post,0,index+1));
root.right = constructFromPrePost(Arrays.copyOfRange(pre,index+2,pre.length),Arrays.copyOfRange(post,index+1,post.length-1));
return root;
}
}

复制代码

二叉查找树BST

* 23. 修剪二叉查找树

669 Trim a Binary Search Tree

https://leetcode.com/problems/trim-a-binary-search-tree/

本题之中使用递归，原理是”修剪“，也就是如何不断舍去不要的节点（不断缩小范围）。下文之中L代表区间左值，R代表区间右值。

那么就分几种情况：

根节点的值直接大于R，那么相应的从根节点到右子树应该全部舍去，直接在左子树上面开始找。
根节点的值直接小于L，那么从根节点到左子树全部舍弃，在右子树上面开始找。
根节点的值在L，R之间，那么需要对其左子树和右子树都进行操作：
- 左节点的值直接变成修剪左子树的返回值
- 右节点的值直接变成修剪右子树的返回值
最后返回节点即可。

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:
Input:

1

/ \

  0 2

  L = 1

  R = 2

Output:

1

   \

   2
复制代码
Example 2:
Input:

3

/ \

  0 4

\

2

/

  1

  L = 1

  R = 3

Output:

   3

   /

2

  /

1
复制代码

class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root==null) return null;
if(root.val>R) return trimBST(root.left,L,R);
if(root.val<L) return trimBST(root.right,L,R);
root.left = trimBST(root.left,L,R);
root.right = trimBST(root.right,L,R);
return root;
}
}

复制代码

*24. 寻找BST的第k个元素

230 Kth Smallest Element in a BST (Medium)

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

BST中序遍历有序，直接借助这一点进行查找第k个元素。

得借助外面的两个变量，一个存储当前遍历到了第几位，一个存储最终的返回结果。

因为我在递归开始的时候就进行了res++，所以判断条件应该是if(res==k)，而不是和k-1做判断。但是，如果是对于借助arrayList来进行结果存储的情况下，需要考虑第n小的元素下标是n-1.

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:
Input: root = [3,1,4,null,2], k = 1

3

  / \

1 4

  \

2

Output: 1
复制代码
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3

   5

   / \

   3 6

/ \

2 4

  /

1

Output: 3
复制代码
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

class Solution {
int res = 0;
int ret=0;
public int kthSmallest(TreeNode root, int k) {
if(root==null) return 0;
inorder(root,k);
return ret;
}
public void inorder(TreeNode node,int k){
if(node ==null) return;
inorder(node.left,k);
res++;
if(res==k){
ret = node.val;
return;
}
inorder(node.right,k);
}
}

复制代码

*25. 将二叉查找树的每个节点的值都加上比它大的节点的值

538 Convert BST to Greater Tree (Easy)

https://leetcode.com/problems/convert-bst-to-greater-tree/

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:
Input: The root of a Binary Search Tree like this:

            5

         / \

         2    13

Output: The root of a Greater Tree like this:

         18

         / \

      20    13
复制代码
Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

解法一

最暴力的解法就是将比一个数字大的所有数字都拿出来，然后相加了。

首先，利用BST的性质，使用一个arrayList来承接按照中序遍历的BST的结果，那么这个arrayList就是天然有序的。

之后，对于每一个TreeNode，找到其在arrayList之中的位置，然后将值变为0（也可以从这个位置往后加来判断，但是这样可能会有边界问题，需要在此判断，我这边省事就直接以0开始）。从这个位置开始向后相加，直到加完，那么一个TreeNode的值就修改好了。

最后，将左右子节点分别这样遍历，最后返回根节点即可。

使用这种方式的时间和空复杂度都较高。

class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public TreeNode convertBST(TreeNode root) {
if(root==null) return null;
middleOrder(root);
helper(root);
return root;
}
public void helper(TreeNode root){
if(root==null) return;
int index = 0;
for(int i=0;i<arrayList.size();i++){
if(arrayList.get(i)==root.val) index = i;
}
root.val = 0;
for(int i=index;i<arrayList.size();i++){
root.val+=arrayList.get(i);
}
helper(root.left);
helper(root.right);
}
public void middleOrder(TreeNode node){
if(node ==null) return;
middleOrder(node.left);
arrayList.add(node.val);
middleOrder(node.right);
}
}

复制代码

* 解法二

根据BST的性质，要去找对于某个节点而言的更大的值，分两种情况：

假设这个节点是左子节点，那么比它大的值是这棵树对应的根节点+右子节点
假设这个节点是根节点，那么比它大的值是这棵树的右子节点

如果使用一个数字作为累加和，那么应该先对右边子节点的值进行累加，这样可以保证操作的时候针对的节点是根节点和右子节点。然后再对于左边的数字进行遍历，这样就能够对于每个左子节点，加上的值都是右子节点+根的值。

所以整个递归过程之中的第一步，应该是对于整棵树的右子节点进行操作，发现其右子节点是空，进行下一步，对于其根节点进行操作，加上这个右子节点的值……这样往复循环。

class Solution {
int sum =0;
public TreeNode convertBST(TreeNode root) {
helper(root);
return root;
}
public void helper(TreeNode root){
if(root==null) return;
helper(root.right);
sum+=root.val;
root.val = sum;
helper(root.left);
}
}

复制代码

* 26. BST的最近公共祖先

235 Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

本题之中讲了，是在BST之中搜索最近的公共祖先，一开始笔者冥思苦想，自己认为要借助两个栈，先遍历，然后将路上遇到的节点入栈，最后不断出栈比较这种形式。这种觉得过于繁杂。

下面这个格式很清晰，就是“只要从上到下遍历，看到了在这两个值之间的节点就直接输出”。

按照二叉树对应看了一下，的确是这样。

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.
复制代码
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

Output: 2

Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
复制代码
Note:

All of the nodes' values will be unique.
p and q are different and both values will exist in the BST.

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right,p,q);
if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left,p,q);
return root;
}
}

复制代码

* 27 二叉树的最近公共祖先

236 Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

说实话，这个题目我拿到是懵逼的，虽然和上面的一个题如此相近，但是这是一个完全没有任何规律的二叉树，也就谈不上使用大小来获取关系了。

在树的递归之中，如何根据不同的场景找到不同的结束条件和返回值是很重要的事情。

本题之中，递归的结束条件有三种：

root==null，意味着这一支已经遍历完毕
root==p，意味着遍历到其中一个的值，再往下没有意义
root==q，和上面这个一样。

三种递归条件结束都是返回root，即条件满足时候的值。

使用递归框架，用left和right来记录左边递归和右边递归的值。

返回值：

if(right==null),意味着这一支遍历完毕，且最后没有得到值。那么无脑返回left。
if(left==null),同上，无脑返回right。
直接返回root。这种情况下left和right都不是null，那么这个时候root就是要的返回值（二者的根）

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.
复制代码
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
复制代码
Note:

All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(right==null){
return left;
}
if(left==null){
return right;
}
return root;
}
}

复制代码

* 28. 从有序数组之中构建BST

108 Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

题目不仅要求BST，而且要求是 height balanced 的 BST。那么我们就不能做一个类似链表的一样的最简单的BST来提交了。

如何尽量保证高度平衡？因为是有序数组，所以尽量每次都取中间的值来产生TreeNode。

本题之中需要自己写一个helper函数，TreeNode helper(int[] nums, int i,int j)。其中，i是起始值，j是终止值。递归的终止条件，就是当i>j的时候，也就是这个数组之中一个值都没有的时候，就直接返回null了。

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

   0

   / \

-3 9

/ /

-10  5
复制代码

class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums,0, nums.length-1);
}
public TreeNode helper(int[] nums, int i,int j){
if(i>j) return null;
int mid = (i+j)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums,i,mid-1);
root.right = helper(nums,mid+1,j);
return root;
}
}

复制代码

* 29. 从有序链表之中恢复BST

109 Convert Sorted List to Binary Search Tree

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

本题和上一题有些相似，但是链表本身如何判断“中位数”？答案是使用快慢指针。

由于要以“中位数”为界限进行分割，所以要得到三个位置的ListNode: 中位数之前，中位数，中位数之后：

以中位数为值进行TreeNode的组建，将中位数之前的ListNode的next设置成null，用来分割链表；以中位数之后的ListNode作为递归的两个起点之一。

所以本题之中比较有趣的是ListNode preMid(ListNode head)，如其含义所示，preMid，就是Mid之前的ListNode。

且其快慢指针不是同时开始，快指针本来就比慢指针快一步。

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

   0

   / \

-3 9

/ /

-10  5
复制代码

class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
if(head.next == null) return new TreeNode(head.val);
ListNode preMid = preMid(head);
TreeNode res = new TreeNode(preMid.next.val);
ListNode midNext = preMid.next.next;
preMid.next = null;
res.left = sortedListToBST(head);
res.right = sortedListToBST(midNext);
return res;
}
public ListNode preMid(ListNode head){
ListNode slow = head;
ListNode fast = head.next;
ListNode preMid = head;
while(fast!=null && fast.next!=null){
preMid = slow;
slow = slow.next;
fast = fast.next.next;
}
return preMid;
}
}

复制代码

30. 二叉树之中寻找两个节点值为一个给定值

653 Two Sum IV - Input is a BST

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

暴力解法，直接生成有序arrayList然后直接双指针。

大佬还有这样一句评语：

“应该注意到，这一题不能用分别在左右子树两部分来处理这种思想，因为两个待求的节点可能分别在左右子树中。”

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:
Input:

5

/ \

3 6

/ \ \

2 4 7

Target = 9

Output: True
复制代码
Example 2:
Input:

5

/ \

3 6

/ \ \

2 4 7

Target = 28

Output: False
复制代码

class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public boolean findTarget(TreeNode root, int k) {
if(root==null) return false;
middleOrder(root);
int i=0,j=arrayList.size()-1;
while(i<j){
int small = arrayList.get(i);
int big = arrayList.get(j);
if(small+big<k) i=i+1;
if(small+big == k) return true;
if(small+big>k) j=j-1;
}
return false;
}
public void middleOrder(TreeNode root){
if(root==null) return;
middleOrder(root.left);
arrayList.add(root.val);
middleOrder(root.right);
}
}

复制代码

31 BST之中两个数的最小差值

530 Minimum Absolute Difference in BST

https://leetcode.com/problems/minimum-absolute-difference-in-bst/

中序遍历之后不断比较相邻两个数字差值即可。

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:
Input:

1

\

3

/

2

Output:

1

Explanation:

The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
复制代码
Note:

There are at least two nodes in this BST.
This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public int getMinimumDifference(TreeNode root) {
if(root==null) return 0;
inorder(root);
int ret = arrayList.get(1)-arrayList.get(0);
for(int i=0;i<arrayList.size()-1;i++){
if(ret>arrayList.get(i+1)-arrayList.get(i)){
ret=arrayList.get(i+1)-arrayList.get(i);
}
}
return ret;
}
public void inorder(TreeNode root){
if(root==null) return;
inorder(root.left);
arrayList.add(root.val);
inorder(root.right);
}
}

复制代码

*32 寻找BST之中出现次数最多的值

501 Find Mode in Binary Search Tree

https://leetcode.com/problems/find-mode-in-binary-search-tree/

本题之中实际上使用了中序遍历来得到按序排列的元素值，然后在中序遍历的节点处理部分做了具体的逻辑操作。

借助三个外部变量，一个curcnt代表当前的节点的出现次数，一个maxcnt代表已知的节点出现次数，一个TreeNode pre用来存储上一次处理的节点。

那么在实际的逻辑:inorder之中，对于当前节点root的处理逻辑是：

如果pre非空，那么比较其和root的关系，如果值相同，那么curcnt+1，如果值不相同，那么直接将curcnt置为1（相当于重新初始化）
比较curcnt和maxcnt的关系，如果curcnt>maxcnt，那么将当前的数组清零，maxcnt=curcnt，且将当前节点的值塞入arrayList。如果相等，那么直接将值塞入arrayList即可。
最后将pre=root，即每次都要更新节点。

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],
1

\

2

/

2
复制代码
return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

class Solution {
int curcnt = 1;
int maxcnt = 1;
TreeNode pre = null;
public int[] findMode(TreeNode root) {
ArrayList<Integer> arrayList = new ArrayList<>();
inorder(root,arrayList);
int[] res = new int[arrayList.size()];
for(int i=0;i<arrayList.size();i++){
res[i]=arrayList.get(i);
}
return res;
}
public void inorder(TreeNode root, List<Integer> nums){
if(root==null) return;
inorder(root.left,nums);
if(pre!=null){
if(pre.val==root.val){
curcnt+=1;
}else{
curcnt=1;
}
}
if(curcnt>maxcnt){
nums.clear();
maxcnt=curcnt;
nums.add(root.val);
}else if(curcnt==maxcnt){
nums.add(root.val);
}
pre = root;
inorder(root.right,nums);
}
}

复制代码

33. 序列化和反序列化二叉树

449 Serialize and Deserialize BST

本题我采用的是层序遍历。因为空的节点在序列化的过程之中也要表示出来，所以序列化和反序列化都需要对null的TreeNode进行特殊的处理。我是将null的地方以"*"表示，恢复的时候也要看当前节点是不是null。

public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null) return "";
ArrayList<Integer> res = layerOrder(root);
StringBuilder sb = new StringBuilder();
for(int i=0;i<res.size();i++){
if(res.get(i)==null){
sb.append("*");
}else{
sb.append(res.get(i));
}
sb.append(" ");
}
sb.deleteCharAt(sb.length()-1);
System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data=="") return null;
String[] strArray = data.split(" ");
int length = strArray.length;
TreeNode root = new TreeNode(Integer.parseInt(strArray[0]));
if(length==1) return root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int counter =1;
while(!queue.isEmpty() && counter<length){
TreeNode node = queue.remove();
if(node!=null){
node.left = changeStringToTreeNode(strArray[counter]);
counter++;
node.right = changeStringToTreeNode(strArray[counter]);
counter++;
queue.add(node.left);
queue.add(node.right);
}
}
return root;
}
public TreeNode changeStringToTreeNode(String s){
if(s.equals("*")) return null;
else{
return new TreeNode(Integer.parseInt(s));
}
}
public ArrayList<Integer> layerOrder(TreeNode node){
ArrayList<Integer> arrayList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
while(!queue.isEmpty()){
int count = queue.size();
for(int i=0;i<count;i++){
TreeNode node1 = queue.remove();
if(node1==null){
arrayList.add(null);
}else{
arrayList.add(node1.val);
queue.add(node1.left);
queue.add(node1.right);
}
}
}
return arrayList;
}
}

复制代码

Trie

* 34 实现Trie

208 Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/

题目要求实现Trie,重点在于Trie的值实际上是在树的“边”上，而非是节点上面。但是二叉树之中又只有节点能存储值，所以借助节点来存储其状态是否为单词已结束。

首先，实现Trie需要一个内部类Node,也需要初始化一个Node作为根节点。这个根节点之中维护着一个Node的长度为26的数组，和一个isLeaf的状态位。如果在添加的过程之中要添加哪个字母，就将相应位置上面的这个Node初始化。那么在查找的时候，如果对应位置上面的Node是null，就意味着这个单词在Trie之中还没出现。如果不是null，实际上意味的是这个边上是有值的。

所有的函数都需要辅助函数，辅助函数之中需要多加一个Node作为参数方便递归，因为每次都会将第一个字母拿走然后再递归相应的节点。

单独写了另一个辅助函数indexOfNode，用来求在数组之中的位置。

Implement a trie with insert, search, and startsWith methods.

Example:
Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // returns true

trie.search("app"); // returns false

trie.startsWith("app"); // returns true

trie.insert("app");

trie.search("app"); // returns true
复制代码
Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

class Trie {
private class Node{
Node[] array = new Node[26];
boolean isLeaf;
}
private Node root = new Node();
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
insert(word,root);
}
private void insert(String word, Node node){
if(node==null) return;
if(word.length()==0) {
node.isLeaf=true;
return;
}
char c= word.charAt(0);
int index = indexOfNode(c);
if(node.array[index]==null){
node.array[index]=new Node();
}
insert(word.substring(1),node.array[index]);
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
return search(word,root);
}
public boolean search(String word, Node node){
if(node==null) return false;
if(word.length()==0) return node.isLeaf;
int index = indexOfNode(word.charAt(0));
if(node.array[index]==null) return false;
return search(word.substring(1),node.array[index]);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return startsWith(prefix, root);
}
public boolean startsWith(String prefix, Node node){
if(node==null) return false;
if(prefix.length()==0) return true;
int index = indexOfNode(prefix.charAt(0));
if(node.array[index]==null) return false;
return startsWith(prefix.substring(1),node.array[index]);
}
public int indexOfNode(char c){
return c-'a';
}
}

复制代码

35 Trie实现求前缀和

677 Map Sum Pairs

https://leetcode.com/problems/map-sum-pairs/

本题之中借助Trie实现。两个方法：insert()和 sum()。

其中insert()是和之前一样的，只是将node之中的boolean isLeaf改成了int val。之外，没有任何改变。

但是int sum(String prefix, Node node)的改变比较大：

首先，将树递归到prefix的长度位0的时候，期间的值不计算。当prefix的值是0的时候，先将当前节点的值赋给sum，然后对其所有子节点进行递归。最后返回sum。

Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

Example 1:
Input: insert("apple", 3), Output: Null

Input: sum("ap"), Output: 3

Input: insert("app", 2), Output: Null

Input: sum("ap"), Output: 5
复制代码

class MapSum {
public class Node{
Node[] array = new Node[26];
int val;
}
private Node root = new Node();
/** Initialize your data structure here. */
public MapSum() {
}
public void insert(String key, int val) {
insert(key,val,root);
}
private void insert(String key, int val, Node node){
if(node==null) return;
if(key.length()==0){
node.val = val;
return;
}
int index = indexOfChar(key.charAt(0));
if(node.array[index]==null){
node.array[index] = new Node();
}
insert(key.substring(1),val,node.array[index]);
}
public int sum(String prefix) {
return sum(prefix,root);
}
private int sum(String prefix, Node node){
if(node==null) return 0;
if(prefix.length()!=0){
Node node1 = node.array[indexOfChar(prefix.charAt(0))];
return sum(prefix.substring(1),node1);
}
int sum = node.val;
for(Node child:node.array){
sum+=sum(prefix,child);
System.out.println(prefix);
}
return sum;
}
private int indexOfChar(char c){
return c-'a';
}
}

复制代码

星空OAOA · 2020-11-13 08:35:14

多谢楼主! 写得很详细

zzh372024750

这种帖子是在是太好了，谢谢楼主的总结，有的时候不得不说，有的时候同学们刷题的进度一开始慢，很多原因就是因为leetcode discussion 有的时候答案不太新人友好

希望楼主继续补坑，期待dp 专题！！！很愿意和楼主一起讨论！！！

在这种政治中心

zzh372024750 发表于 2020-6-19 00:42
这种帖子是在是太好了，谢谢楼主的总结，有的时候不得不说，有的时候同学们刷题的进度一开始慢，很多原因就 ...

多谢您！的确是自己在刷题的路上尤其是初期刷题的路上会遇到很多坑，所以把自己的一些**心得发出来，不会有那种秀操作的“一句式”答案。等到dp部分有迷茫的还要互相讨教，哈哈~

shawn_lyu

Good post! lz用心了。
如果可以的话我在这里做一点补充，关于如何按照前序、中序、后序分别采用iteration和recursion的方法遍历二叉树，以及代码。
https://shawnlyu.com/algorithms/40/

晚鱼Iris

收藏楼主的个人博了～

在这种政治中心

shawn_lyu 发表于 2020-6-22 10:43
Good post! lz用心了。
如果可以的话我在这里做一点补充，关于如何按照前序、中序、后序分别采用iteration ...

多谢您的补充~一起成长一起进步呀

在这种政治中心

晚鱼Iris 发表于 2020-6-22 12:22
收藏楼主的个人博了～

多谢您的收藏~博客上面会更新很多自己的心得，也希望和您相互交流~

在这种政治中心 · 2020-12-12 16:56:39

星空OAOA 发表于 2020-11-13 08:35
多谢楼主! 写得很详细

谢谢您~希望可以共同进步！

在这种政治中心

本帖最后由在这种政治中心于 2025-6-4 11:56 编辑

94. Binary Tree Inorder Traversal
The inorder traversal of the binary tree is that "left-root-right". So this is a classic question for recursion.
For one binary tree, if it reached the leaf layer, it will got "null" node. So here is the way:class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList();
      helper(root, res);
      return res;
}

public void helper(TreeNode root, List<Integer> res) {
      if (root != null) {
         helper(root.left, res);
         res.add(root.val);
         helper(root.right, res);
      }
}
}

So for the inorder traversal, it is the left child will always be traversed before the right. So in the code we just traverse the left side first. No need to worry some "mixed" situation for making the solving more complex

100. Same Tree
Here is to compare 2 trees are the same. Actually the solution can just change a little and support not only the binary trees, but also all the trees.class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
         return true;
      }
      if (p == null || q == null || (p.val != q.val)) {
         return false;
      }
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

}
Also simple solution: compare the node itself first, then left sub tree, then right sub tree.
101. Symmetric Tree
symmetric means 'made up of exactly similar parts facing each other or around an axis;',class Solution {
public boolean isSymmetric(TreeNode root) {
      if (root == null)
         return true;
      return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
         return true;
      }
      if (p == null || q == null || (p.val != q.val)) {
         return false;
      }

      return isMirror(p.left, q.right) && isMirror(p.right, q.left);
}
}
For some normal questions, we only need to consider the current layer and the next layer. But for this, we need to consider the current layer, next layer also the subtrees for next layer.
104. Maximum Depth of Binary Tree
For max depth, it is the max depth of (left subtree , right subtree) + 1, because need to consider the root node.class Solution {
public int maxDepth(TreeNode root) {
      if (root == null)
         return 0;
      return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

补充内容 (2025-06-04 11:55 +08:00):

94. Binary Tree Inorder Traversal
The inorder traversal of the binary tree is that "left-root-right". So this is a classic question for recursion.
For one binary tree, if it reached the leaf layer, it will got "null" node. So here is the way:class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList();
      helper(root, res);
      return res;
}

public void helper(TreeNode root, List<Integer> res) {
      if (root != null) {
         helper(root.left, res);
         res.add(root.val);
         helper(root.right, res);
      }
}
}

So for the inorder traversal, it is the left child will always be traversed before the right. So in the code we just traverse the left side first. No need to worry some "mixed" situation for making the solving more complex

100. Same Tree
Here is to compare 2 trees are the same. Actually the solution can just change a little and support not only the binary trees, but also all the trees.class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
         return true;
      }
      if (p == null || q == null || (p.val != q.val)) {
         return false;
      }
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

}
Also simple solution: compare the node itself first, then left sub tree, then right sub tree.
101. Symmetric Tree
symmetric means 'made up of exactly similar parts facing each other or around an axis;',class Solution {
public boolean isSymmetric(TreeNode root) {
      if (root == null)
         return true;
      return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
         return true;
      }
      if (p == null || q == null || (p.val != q.val)) {
         return false;
      }

      return isMirror(p.left, q.right) && isMirror(p.right, q.left);
}
}
For some normal questions, we only need to consider the current layer and the next layer. But for this, we need to consider the current layer, next layer also the subtrees for next layer.
104. Maximum Depth of Binary Tree
For max depth, it is the max depth of (left subtree , right subtree) + 1, because need to consider the root node.class Solution {
public int maxDepth(TreeNode root) {
      if (root == null)
         return 0;
      return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
257. Binary Tree Paths
Same as above, but just change logics for the tree path. Not just calculate the depth, but also need to add the value to the return arraylist.

[/quote]
补充内容 (2025-06-04 11:55 +08:00):

94. Binary Tree Inorder Traversal
The inorder traversal of the binary tree is that "left-root-right". So this is a classic question for recursion.
For one binary tree, if it reached the leaf layer, it will got "null" node. So here is the way:class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList();
      helper(root, res);
      return res;
}

public void helper(TreeNode root, List<Integer> res) {
      if (root != null) {
         helper(root.left, res);
         res.add(root.val);
         helper(root.right, res);
      }
}
}[quote]
So for the inorder traversal, it is the left child will always be traversed before the right. So in the code we just traverse the left side first. No need to worry some "mixed" situation for making the solving more complex

100. Same Tree
Here is to compare 2 trees are the same. Actually the solution can just change a little and support not only the binary trees, but also all the trees.class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
         return true;
      }
      if (p == null || q == null || (p.val != q.val)) {
         return false;
      }
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

}
Also simple solution: compare the node itself first, then left sub tree, then right sub tree.
101. Symmetric Tree
symmetric means 'made up of exactly similar parts facing each other or around an axis;',class Solution {
public boolean isSymmetric(TreeNode root) {
      if (root == null)
         return true;
      return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode p, TreeNode q) {
      if (p == null && q == null) {
         return true;
      }
      if (p == null || q == null || (p.val != q.val)) {
         return false;
      }

      return isMirror(p.left, q.right) && isMirror(p.right, q.left);
}
}
For some normal questions, we only need to consider the current layer and the next layer. But for this, we need to consider the current layer, next layer also the subtrees for next layer.
104. Maximum Depth of Binary Tree
For max depth, it is the max depth of (left subtree , right subtree) + 1, because need to consider the root node.class Solution {
public int maxDepth(TreeNode root) {
      if (root == null)
         return 0;
      return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
257. Binary Tree Paths
Same as above, but just change logics for the tree path. Not just calculate the depth, but also need to add the value to the return arraylist.

[树/链表/图] 负基础入门leetcode二叉树相关题解+思路（二）

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

评分

评分

浏览过的版块