2022-8-30 每日一题-二叉树递归-

标签：TreeNode val int 30 Construct 二叉树 2022 root 节点

998. 最大二叉树 II

难度中等90收藏分享切换为英文接收动态反馈

最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。

给你最大树的根节点 root 和一个整数 val 。

就像 之前的问题 那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：

• 如果 a 为空，返回 null 。
• 否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
• root 的左子树将被构建为 Construct([a[0], a[1], ..., a[i - 1]]) 。
• root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]) 。
• 返回 root 。

请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。

假设 b 是 a 的副本，并在末尾附加值 val。题目数据保证 b 中的值互不相同。

返回 Construct(b) 。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public TreeNode insertIntoMaxTree(TreeNode root, int val) {
18         if (root==null) return null;
19         if (root.val<val){
20             TreeNode node=new TreeNode(val);
21             node.left=root;
22             return node;
23         }else{
24             TreeNode node=insertIntoMaxTree(root.right,val);
25             if (node!=null) root.right=node;
26             else root.right=new TreeNode(val);
27             return root;
28         }
29     }
30 }

思路：如果当前值最大，直接接在新root后面，否则递归的在右子树中添加返回根节点，如果是null说明没有比他小的子树了，直接加到根节点的右边，否则将新的root接在右边。

剑指 Offer II 067. 最大的异或

难度中等44收藏分享切换为英文接收动态反馈

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 1 public class Solution {
 2     Trie root;
 3     public int findMaximumXOR(int[] nums) {
 4         root=new Trie();
 5         int x=0;
 6         for (int i=1;i<nums.length;i++){
 7             add(nums[i-1]);
 8             x=Math.max(x,com(nums[i]));
 9         }
10         return x;
11     }
12 
13     public void add(int x){
14         Trie trie=root;
15         for (int i=30;i>=0;i--){
16             int bit=(1<<i)&x;
17             if (bit==0){
18                 if (trie.left==null) trie.left=new Trie();
19                 trie=trie.left;
20             }else{
21                 if (trie.right==null) trie.right=new Trie();
22                 trie=trie.right;
23             }
24         }
25     }
26 
27     public int com(int num){
28         Trie trie=root;
29         int x=0;
30         for (int i=30;i>=0;i--){
31             int bit=(1<<i)&num;
32             if (bit==0){
33                 if (trie.right!=null){
34                     x=x*2+1;
35                     trie=trie.right;
36                 }else{
37                     x=x*2;
38                     trie=trie.left;
39                 }
40             }else{
41                 if (trie.left!=null){
42                     x=x*2+1;
43                     trie=trie.left;
44                 }else{
45                     x=x*2;
46                     trie=trie.right;
47                 }
48             }
49         }
50         return x;
51     }
52 
53 
54 }
55 class Trie{
56     Trie left;
57     Trie right;
58     Trie(){
59         left=null;
60         right=null;
61     }
62 }

思路：字典树，将数字看成31位的字符串，从高位选取最优的选择得到最大的x。

 

标签：TreeNode,val,int,30,Construct,二叉树,2022,root,节点
From： https://www.cnblogs.com/benbicao/p/16638778.html