力扣-数据结构-8【算法学习day.79】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

今天开始复习树,简单的题目不会具体分析

习题

1.二叉树的前序遍历

题目链接:144. 二叉树的前序遍历 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> ans = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {recursion(root);return ans;}public void recursion(TreeNode node){if(node==null)return;ans.add(node.val);recursion(node.left);recursion(node.right);}
}

2. 叶子相似的树

题目链接:872. 叶子相似的树 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> list1 = new ArrayList<>();List<Integer> list2 = new ArrayList<>();public boolean leafSimilar(TreeNode root1, TreeNode root2) {recursion(root1,1);recursion(root2,2);if(list1.size()!=list2.size())return false;for(int i = 0;i<list1.size();i++){if(!list1.get(i).equals(list2.get(i)))return false;}return true;}public void recursion(TreeNode node,int flag){if(node==null)return;if(node.left==null&&node.right==null){if(flag==1){list1.add(node.val);}else{list2.add(node.val);}return;}recursion(node.left,flag);recursion(node.right,flag);}
}

3.开幕式焰火

题目链接: LCP 44. 开幕式焰火 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {Map<Integer,Integer> map = new HashMap<>();int ans = 0;public int numColor(TreeNode root) {recursion(root);return ans;}public void recursion(TreeNode node){if(node==null)return;recursion(node.left);recursion(node.right);if(map.getOrDefault(node.val,-1)==-1){ans++;map.merge(node.val,1,Integer::sum);}}
}

4.二叉树中第二小的节点

题目链接: 671. 二叉树中第二小的节点 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int[] arr= new int[30];int count = 0;public int findSecondMinimumValue(TreeNode root) {recursion(root);Arrays.sort(arr);int index = 0;while(arr[index]==0)index++;int first = arr[index];//    System.out.println(first);while(index<=29&&arr[index]==first)index++;return index==30?-1:arr[index];}public void recursion(TreeNode node){if(node==null)return;arr[count++] = node.val;recursion(node.left);recursion(node.right);}
}

5.求根节点到叶子节点数字之和

题目链接: 129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans = 0;public int sumNumbers(TreeNode root) {recursion(root,0);return ans;}public void recursion(TreeNode node,int val){if(node==null)return;val=val*10+node.val;if(node.left==null&&node.right==null){ans+=val;return;}recursion(node.left,val);recursion(node.right,val);}
}

6.统计二叉树中好节点的数目

题目链接: 1448. 统计二叉树中好节点的数目 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans =0;public int goodNodes(TreeNode root) {recursion(root,Integer.MIN_VALUE);return ans;}public void recursion(TreeNode node,int max){if(node==null)return;if(node.val>=max){// System.out.println(node.val);ans++;max = node.val;}recursion(node.left,max);recursion(node.right,max);}
}

7.二叉树中的伪回文路径

题目链接:1457. 二叉树中的伪回文路径 - 力扣（LeetCode）

题面:

分析：由于节点的值从1到9，所以可以用一个数组存遍历到的数的个数，遍历到尾节点的时候遍历数组，如果数组中奇数次数的个数超过1个，就无法构成回文

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans = 0;public int pseudoPalindromicPaths (TreeNode root) {int[] arr = new int[10];recursion(root,arr);return ans;}public void recursion(TreeNode node, int[] arr){if(node==null)return;arr[node.val]++;if(node.left==null&&node.right==null){int count = 0;for(int a:arr){if(a%2==1)count++;}if(count<=1)ans++;arr[node.val]--;return;}recursion(node.left,arr);recursion(node.right,arr);arr[node.val]--;}
}

8.祖父节点值为偶数的节点和

题目链接: 1315. 祖父节点值为偶数的节点和 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans = 0;public int sumEvenGrandparent(TreeNode root) {recursion(root,-1,-1);return ans;}public void recursion(TreeNode node,int par,int gpar){if(node==null)return;if(gpar!=-1&&gpar%2==0){ans+=node.val;}recursion(node.left,node.val,par);recursion(node.right,node.val,par);}
}

9.从叶节点开始的最小字符串

题目链接: 988. 从叶结点开始的最小字符串 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {String ans = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";public String smallestFromLeaf(TreeNode root) {recursion(root,"");return new StringBuilder().append(ans).reverse().toString();}public void recursion(TreeNode node,String str){if(node==null)return;int flag = 'a'+node.val;str+=(char)flag;if(node.left==null&&node.right==null){ans = compareToString(str,ans)?ans:str;return;}recursion(node.left,str);recursion(node.right,str);}public Boolean compareToString(String str1,String str2){char[] arr1 = str1.toCharArray();char[] arr2 = str2.toCharArray();int l1 = arr1.length-1;int l2 = arr2.length-1;while(l1>=0&&l2>=0){if(arr1[l1]>arr2[l2]){return true;}else if(arr1[l1]<arr2[l2]){return false;}l1--;l2--;}return l1==-1?false:true;}
}

10.节点与其祖先之间的最大差值

题目链接: 1026. 节点与其祖先之间的最大差值 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans = 0;public int maxAncestorDiff(TreeNode root) {recursion(root,Integer.MAX_VALUE,Integer.MIN_VALUE);return ans;}public void recursion(TreeNode node,int min,int max){if(node==null)return;if(min!=Integer.MAX_VALUE){ans = Math.max(ans,Math.abs(min-node.val));}if(max!=Integer.MIN_VALUE){ans = Math.max(ans,Math.abs(max-node.val));}recursion(node.left,Math.min(min,node.val),Math.max(max,node.val));recursion(node.right,Math.min(min,node.val),Math.max(max,node.val));}
}

11.从根到叶的二进制数之和

题目链接: 1022. 从根到叶的二进制数之和 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int ans = 0;public int sumRootToLeaf(TreeNode root) {recursion(root,0);return ans;}public void recursion(TreeNode node,int sum){if(node==null)return;sum = (sum<<1)+node.val;// System.out.println(sum);if(node.left==null&&node.right==null){ans+=sum;return;}recursion(node.left,sum);recursion(node.right,sum);}
}

12.在二叉树中增加一行

题目链接: 623. 在二叉树中增加一行 - 力扣（LeetCode）

题面:

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode addOneRow(TreeNode root, int val, int depth) {if(depth==1){TreeNode node = new TreeNode(val);node.left  = root;return node;}Queue<TreeNode> queue = new LinkedList<>();int indexdepth = 2;queue.offer(root);Queue<TreeNode> queue2 = new LinkedList<>();while(indexdepth<depth){while(!queue.isEmpty()){TreeNode node = queue.poll();if(node.left!=null){queue2.offer(node.left);}if(node.right!=null){queue2.offer(node.right);}}queue = queue2;queue2 = new LinkedList<>();indexdepth++;}while(!queue.isEmpty()){TreeNode node = queue.poll();TreeNode left = node.left;TreeNode right = node.right;node.left = new TreeNode(val);node.right = new TreeNode(val);node.left.left = left;node.right.right = right;}return root;}
}