LeetCode 笔记--- 二叉树
501.求BST的众数
这个题不需要另外定义一个map 会造成空间的浪费 因为根据BST的特性 中序遍历 相同的元素都是排在一起的 所以只需要维护一个maxNum curNum cur
遍历到不同的元素 就刷新cur curnum复位为1 并且和Maxnum比较 如果相同 就加入到结果数组 如果不相同 就把结果数组清空 再加入
private int cur;
private int curNum;
private int maxNum=-1;
private List<Integer>res;
public int[] findMode(TreeNode root) {
res=new ArrayList<>();
dfs(root);
int []ans=new int[res.size()];
if (res.size()>0)
for (int i = 0; i < ans.length; i++)
{
ans[i]=res.get(i);
}
return ans;
}
public void dfs(TreeNode root)
{
if (root==null)return ;
dfs(root.left);
update(root.val);
dfs(root.right);
}
public void update(int val)
{
if (val!=cur)
{
cur=val;
curNum=1;
}
else
{
curNum++;
}
if (curNum>maxNum)
{
res.clear();
res.add(cur);
maxNum=curNum;
}
else if (curNum<maxNum)
{
}
else
{
res.add(cur);
}
}
109.有序链表转化为BST
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
快慢指针加分治法
首先求出链表的中间节点作为树的根节点 然后以Mid节点为界 对左右两个链表采取同样的方法
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head,null);
}
public TreeNode buildTree(ListNode left,ListNode right)
{
if (left==right)return null;
ListNode mid = findMidListNode(left, right);
TreeNode newNode = new TreeNode(mid.val);
newNode.left=buildTree(left,mid);
newNode.right=buildTree(mid.next,right);
return newNode;
}
public ListNode findMidListNode(ListNode left,ListNode right)
{
if (left==right)return null;
ListNode slow=left;
ListNode fast=left;
while (fast!=right&&fast.next!=right)
{
slow=slow.next;
fast=fast.next;
fast=fast.next;
}
return slow;
}
538.把二叉搜索树转化为累加树
要把一个BST转化为每个节点值变成大于等于原节点元素的树 只需要倒序遍历 维护一个sum变量 到哪个点了就root.val=root.val+sum
tips 这里的倒序不是说的后序遍历 而是说 逆中序遍历 即为先遍历right子树
230.求二叉搜索树的第K个最小的元素
这个题就是中序遍历 然后用一个hasReadNum作为标志表示当前你已经遍历到第几个元素了 如果是第k个 返回就是了 如果大于 直接返回 相当于剪枝
private int hasReadNum;
int res;
public int kthSmallest(TreeNode root, int k) {
res=0;
hasReadNum=0;
dfs(root,k);
return res;
}
public void dfs(TreeNode root,int k)
{
if (root==null)return ;
dfs(root.left,k);
hasReadNum++;
if (hasReadNum==k)
{
res=root.val;
return ;
}
else if (hasReadNum>k)
{
return;
}
dfs(root.right,k);
}
669.修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
思路: 假设trimBST的结果是理想的 判断一下我当前节点 的值 如果root.val<l说明只需要考虑右子树 左子树已经不符合了 这是搜索树的性质 同理 如果root.val>R 那只需要判断左子树
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root==null)return null;
if (root.val>high)return trimBST(root.left,low,high);
if (root.val<low)return trimBST(root.right,low,high);
root.left=trimBST(root.left,low,high);
root.right=trimBST(root.right,low,high);
return root;
}
637.二叉树的层平均值
BFS遍历每一层 需要注意的是 每一次Poll元素之前先记录一下此时的queue有多少个元素 这个个数就是本层有多少个元素 sum就+ 这么多次 然后sum/num 就是本层平均值了 在循环内部其实还是正常的BFS该添加元素就元素 因为队列的特性是可以记录的每一层的 513题的找最后一层最左边的元素也是这个方法 判断i==0 也就是每一层的第一个元素的时候 就更新一次答案就行了
public List<Double> averageOfLevels(TreeNode root) {
if (root==null)return null;
List<Double>averages=new ArrayList<>();
Queue<TreeNode>queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty())
{
long levelSum=0;
int levelNum=queue.size();
for (int i = 0; i < levelNum; i++)
{
TreeNode top = queue.poll();
levelSum+=top.val;
if (top.left!=null)queue.add(top.left);
if (top.right!=null)queue.add(top.right);
}
averages.add(levelSum/(levelNum*1.0));
}
return averages;
}
687.最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示
也是找2个节点之间的一条路径 这条路径上的所有的节点的值都是相同的
private int max=Integer.MIN_VALUE;
public int longestUnivaluePath(TreeNode root) {
if (root==null)return 0;
postOrder(root);
return max;
}
public int postOrder(TreeNode root)
{
if (root==null)
{
return 0;
}
int leftArrow=0;
int rightArrow=0;
int leftValue=postOrder(root.left);
int rightValue=postOrder(root.right);
if (root.left!=null&&root.left.val==root.val)
{
leftArrow=(leftValue+1);
}
if (root.right!=null&&root.right.val==root.val)
{
rightArrow=(rightValue+1);
}
max=Math.max(max,leftArrow+rightArrow);
return Math.max(leftArrow,rightArrow);
}
这个题和以前的求最长的路径有点像
递归回溯每个节点 返回的都是这个节点上 左右单支能够取到的最长路径的长度
如果我本节点的值和我的左子树的最长同值路径相等 那就让leftArrow=leftValue+1 也就是得到了现在的左边的最长的同值路径 同理可以得到最长的右边的同值路径 leftArrow 把这俩加起来 同max做比较 更新max的值 最后对于这个节点 返回的还是leftarrow 和rightarrow中较大的那个 因为只能取单边路径
404.左叶子之和
private int sum;
public int sumOfLeftLeaves(TreeNode root) {
sum=0;
fun(root,false);
return sum;
}
public void fun(TreeNode root,boolean isLeft)
{
if (root==null)return ;
if (isLeft&&root.left==null&&root.right==null)
{
sum+=root.val;
return ;
}
fun(root.left,true);
fun(root.right,false);
}
101.对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
一棵树满足镜像对称 就是说他的两个子树需要镜像对称
两颗树需要镜像对称 条件有三个
- 根节点的值相等
- a树的左子树与b树的右子树镜像对称
- a树的右子树与b树的左子树镜像对称
如此一来就可以写成递归的形式了
public boolean isSymmetric(TreeNode root) {
if (root==null)return true;
return twoTreeIsMirroring(root.left,root.right);
}
public boolean twoTreeIsMirroring(TreeNode t1,TreeNode t2)
{
if (t1==null&&t2==null)return true;
if (t1==null||t2==null)return false;
return t1.val==t2.val&&twoTreeIsMirroring(t1.left, t2.right)&&twoTreeIsMirroring(t1.right,t2.left);
}
572.另一个树的子树
暴力解法写了 还没写更好的算法测试
暴力法如下
遍历第一棵树的每个节点依次判断这个节点为root的子树是否与另外一颗树相等
treeEquals就是判断相等的方法
public boolean isSubtree(TreeNode s, TreeNode t) {
if (t==null)return true;
/**
* 如果t等于null 那么t就是任何树的子树 因为 任何一棵树都有null节点
*/
if (s==null)return false;
/**
* 如果s==null 那么s不可能有子树 除非t也等于null 但是这种情况在前面已经是判断了的
*/
return treeEquals(s, t)||isSubtree(s.left,t)||isSubtree(s.right,t);
}
/**
* 判断树是否相等的递归函数
* @param t1
* @param t2
* @return
*/
public boolean treeEquals(TreeNode t1,TreeNode t2)
{
if (t1==null)return t2==null; //同时为null 相等
if (t2==null)return false; //后面的为Null 就不相等
if (t1.val!=t2.val)return false; //两个根节点的值不相等那就是两棵树不相等
/**
* 然后递归 左子树和柚子树 只有左右子树同时相等 树才能相等
*/
return treeEquals(t1.left,t2.left)&&treeEquals(t1.right,t2.right);
}
112.路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
这个题符合递归的思想 要找树的路径上的节点值之和是否等于某个值sum 换个角度来说 就是找 左右子树有的路径上的节点之和是否等于某个sum-root.val
递归终点就是 如果当前是叶子节点了 就判断当前的root.val是否等于sum
public boolean hasPathSum(TreeNode root, int sum) {
if (root==null)return false;
if (root.left==null&&root.right==null)return sum==root.val;
return (hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val));
}
非递归写法 利用广度优先遍历 把每个节点到root节点的节点值之和存起来 两个队列里面11对应 遍历到叶子节点就判断一下 如果满足条件就返回
如果遍历完了都没返回 说明不存在 就返回 false
public boolean hasPathSum(TreeNode root, int sum) {
if (root==null)return false;
Queue<TreeNode> nodeQueue=new ArrayDeque<>();
Queue<Integer>pathQueue=new ArrayDeque<>();
nodeQueue.add(root);
pathQueue.add(root.val);
while (!nodeQueue.isEmpty())
{
TreeNode cur=nodeQueue.poll();
int curSum=pathQueue.poll();
if (cur.left==null&&cur.right==null&&curSum==sum)
return true;
if (cur.left!=null)
{
nodeQueue.add(cur.left);
pathQueue.add(curSum+cur.left.val);
}
if (cur.right!=null)
{
nodeQueue.add(cur.right);
pathQueue.add(curSum+cur.right.val);
}
}
return false;
}
617.合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1==null&&t2==null)return null;
else if (t1==null)return t2;
else if (t2==null)return t1;
else
{
TreeNode newNode = new TreeNode(t1.val + t2.val);
newNode.left=mergeTrees(t1.left,t2.left);
newNode.right=mergeTrees(t1.right,t2.right);
return newNode;
}
}
226.翻转二叉树
public TreeNode invertTree(TreeNode root) {
invertTreeNode(root);
return root;
}
public void invertTreeNode(TreeNode root)
{
if (root==null)return ;
invertTree(root.left);
invertTree(root.right);
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
}
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
刷完这个题说明我已经超越了世界级大牛了
543.二叉树的直径
二叉树的直径定义为任意两个节点之间的距离的最大值
做法就是递归二叉树 返回左右子树种 单支的长度的较大值+1 就是本节点开始的单支的长度 然后维护一个max值 每次遍历到节点就更新一次max的值 max与left单支的长度+right单支的长度+1 比较 取较大值 其实这个题可以看成是 找所有的节点中左右字数高度和最长的那个节点
代码如下
int max;
public int diameterOfBinaryTree(TreeNode root)
{
if (root==null)return 0;
maxDanZhi(root);
return max-1;
}
public int maxDanZhi(TreeNode root)
{
if (root==null)return 0;
int left=maxDanZhi(root.left);
int right=maxDanZhi(root.right);
max=Math.max(max,left+right+1);
return Math.max(left,right)+1;
}
110.判断一棵二叉树是否是平衡二叉树
最优的方法是采用后序遍历 统计左右子树的深度 如果左右子树的深度有一个是-1 说明在子树里面有已经有节点不满足平衡二叉树的定义了 那这棵树也返回-1就可以了 如果 两个深度都不是-1 那就判断他们的差是不是0或者1,如果不是 又不满足 还是返回-1 满足的话 则求出本树的深度 即为max(左子树的深度,右子树的深度)+1;
public int postOrder(TreeNode root)
{
if (root==null)return 0;
int leftDepth=postOrder(root.left);
if (leftDepth==-1)return -1;
int rightDepth=postOrder(root.right);
if (rightDepth==-1)return -1;
return Math.abs(leftDepth-rightDepth)<2?Math.max(leftDepth,rightDepth)+1:-1;
}
public boolean isBalanced(TreeNode root)
{
return postOrder(root)!=-1;
}
104.二叉树的最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
二叉树的深度=max(左子树的深度右子树的深度)+1
public int maxDepth(TreeNode root) {
if (root==null)return 0;
return Integer.max(maxDepth(root.left),maxDepth(root.right))+1;
}