随想录笔记-二叉树练习题

合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

dfs递归

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null||root2==null){return root1==null?root2:root1;}return  dfs(root1,root2);}public TreeNode dfs(TreeNode root1, TreeNode root2){if(root1==null||root2==null){return root1==null?root2:root1;}root1.val+=root2.val;root1.left=dfs(root1.left,root2.left);root1.right=dfs(root1.right,root2.right);return root1;}
}

类似的思路-对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

class Solution {public boolean isSymmetric(TreeNode root) {if(root==null) return true;return compare(root.left,root.right);
}public boolean compare(TreeNode left,TreeNode right){if(left==null&&right!=null) return false;if(left!=null&&right==null) return false;if(left==null&&right==null) return true;if(left.val!=right.val) return false;boolean inner=compare(left.right,right.left);boolean outside=compare(left.left,right.right);return inner&&outside;}
}

bfs迭代

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null||root2==null){return root1==null?root2:root1;}Queue<TreeNode> queue=new LinkedList<TreeNode>();queue.offer(root1);queue.offer(root2);while(!queue.isEmpty()){int len=queue.size();TreeNode t1=queue.poll();TreeNode t2=queue.poll();t1.val+=t2.val;if(t1.left!=null&&t2.left!=null){queue.offer(t1.left);queue.offer(t2.left);}else if(t1.left==null){t1.left=t2.left;}if(t1.right!=null&&t2.right!=null){queue.offer(t1.right);queue.offer(t2.right);}else if(t1.right==null){t1.right=t2.right;}}return root1;}
}

二叉搜索数中的搜索

利用二叉树的性质

首先我们需要知道 二叉搜索树 的一个关键性质：

二叉搜索树任意节点的左子树上所有节点值都小于这个节点；
二叉搜索树任意节点的右子树上所有节点值都大于这个节点；

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root==null||root.val==val) return root;if(root.val>val) return searchBST(root.left,val);return searchBST(root.right,val);}
}

验证二叉搜索数

98. 验证二叉搜索树 - 力扣（LeetCode）

中序遍历

二叉搜索树的性质出发，中序遍历的情况下，后一个数比前一个数大

所以这里面的pre处理的非常好

98. 验证二叉搜索树 - 力扣（LeetCode）

 */
class Solution {long pre=Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root==null) return true;if(!isValidBST(root.left))return false;if(root.val<=pre)return false;pre=root.val;return isValidBST(root.right);}
}

前序遍历

这个代码我自己写的，但是我写的时候没有把边界作为参数传递进去，所以就无法判断子树与根节点的情况，只能判断以以子节点为根节点的数的情况

class Solution {public boolean isValidBST(TreeNode root) {if(root==null) return true;return deal(root,Long.MAX_VALUE,Long.MIN_VALUE);}public boolean deal(TreeNode root,long max,long min){if(root==null) return true;if(root.val<=min||root.val>=max) return false;return deal(root.left,root.val,min)&&deal(root.right,max,root.val);}
}

二叉搜索树的最小绝对差

 min(root.left);
        if(pre!=Integer.MIN_VALUE){
            min=Math.min(min,Math.abs(root.val-pre));
        }
        pre=root.val;
  
        min(root.right);

 pre=root.val;回到根节点

要知道二叉搜索树和中序遍历是好朋友！

class Solution {int min=Integer.MAX_VALUE;int pre=Integer.MIN_VALUE;public int getMinimumDifference(TreeNode root) {min(root);return min;}public void min(TreeNode root){if(root==null) return ;min(root.left);if(pre!=Integer.MIN_VALUE){min=Math.min(min,Math.abs(root.val-pre));}pre=root.val;min(root.right);}
}

二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

 根据二叉搜索树的特点 ，对其进行中序遍历，得到一个有序数组，然后寻找重复的元素

注意！！这个的众数是出现频率最高的数，不是重复的数就是众数

class Solution {HashMap<Integer,Integer> map=new HashMap<>();public int[] findMode(TreeNode root) {List<Integer> list=new ArrayList<>();inorder(root,list);int pre=list.get(0);int len=1;int maxlen=1;List<Integer> res=new ArrayList<>();res.add(list.get(0));for(int i=1;i<list.size();i++){if(list.get(i)==pre){len=len+1;}else{len=1;}if(len==maxlen){res.add(list.get(i));}else if(len>maxlen){maxlen=len;res.clear();res.add(list.get(i));}pre=list.get(i);}return res.stream().mapToInt(Integer::intValue).toArray();}public void inorder(TreeNode root,List<Integer> list){if(root==null)return ;inorder(root.left,list);list.add(root.val);inorder(root.right,list);}}

这个代码就是前一个代码的优化，在中序操作的时候把重复元素找出来，所以执行时间更快

501. 二叉搜索树中的众数 - 力扣（LeetCode）

class Solution {int maxCount = 1;int count = 1;TreeNode preNode = null;    // 存储前一个结点List<Integer> list = new ArrayList();   // 结果集public int[] findMode(TreeNode root) {// 中序遍历中，相同的元素都是一起出现的inOrder(root);int res[] = new int[list.size()];for(int i=0;i<list.size();i++) {res[i] = list.get(i);}return res;}public void inOrder(TreeNode root) {if(root == null) return ;inOrder(root.left);// 中序遍历的处理逻辑if(preNode!=null) {  // 非第一个元素的处理逻辑// 判断当前元素与前一个元素的关系，如果相同count++,不相同重新开始计数if(root.val==preNode.val) count++;else count=1;// 判断当前计数器与最大数的关系，如果相等就加入list，大于就清空list并加入if(count>maxCount) {maxCount = count;list.clear();list.add(root.val);} else if(count==maxCount) 

二叉树的最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

迭代

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

递归

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