做外贸c2c网站有哪些,旅游网站建设的论文,环境文化建设方案网站,网站建设建设公司哪家好leetcode 150道题 计划花两个月时候刷完#xff0c;今天#xff08;第三十五天#xff09;完成了6道(72-77)150#xff1a;
72.(236. 二叉树的最近公共祖先) 题目描述#xff1a;
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义…leetcode 150道题 计划花两个月时候刷完今天第三十五天完成了6道(72-77)150
72.(236. 二叉树的最近公共祖先) 题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”第一版去查了百度百科然后就有了我的一坨代码。。。
class Solution {MapTreeNode,ListTreeNode mapnew HashMap();TreeNode grandTreeNodenull;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(pq){return p;}dfs(root,p,q);return grandTreeNode;}public void dfs(TreeNode root, TreeNode p, TreeNode q) {if(rootnull){return ;}dfs(root.left,p,q);dfs(root.right,p,q);if(grandTreeNode!null){return;}ListTreeNode tempnew ArrayList();if(root.left!nullmap.get(root.left)!null){temp.addAll(map.get(root.left));temp.add(root.left);}if(root.right!nullmap.get(root.right)!null){temp.addAll(map.get(root.right));temp.add(root.right);}if(proottemp.contains(q)){grandTreeNodep;return;}if(qroottemp.contains(p)){grandTreeNodeq;return;}if(temp.contains(p)temp.contains(q)){grandTreeNoderoot;return;}map.put(root,temp);}
}第二版看了解题也没看懂然后看评论区有个好理解的版本就试了一下真不错,谁先找到谁就是头都没找到那就是上一个递归
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull||rootp||rootq){return root;}TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);if(left!nullright!null){return root;}else if(left!null){return left;}else if(right!null){return right;}return null;}
}73-76 全是 二叉树的层次遍历我放下面先放 77
77.530. 二叉搜索树的最小绝对差题目描述
给你一个二叉搜索树的根节点 root 返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数其数值等于两值之差的绝对值。第一版看重点是二叉搜索树他的中序遍历是有序的我不信这题是简单题。。。
class Solution {public int getMinimumDifference(TreeNode root) {//中序遍历if(rootnull){return 0;}TreeNode preNodenull;int minInteger.MAX_VALUE;StackTreeNode stacknew Stack();while(!stack.isEmpty()||root!null){while(root!null){stack.push(root);rootroot.left;}rootstack.pop();if(preNode!null){minMath.min(min,Math.abs(preNode.val-root.val));}preNoderoot;rootroot.right;}return min;}
}73.199. 二叉树的右视图题目描述
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。第一版就是层次遍在这里插入代码片历每次输出这一层的最后一个
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger resnew ArrayList();if(rootnull){return res;}//层次遍历 输出最后一个LinkedListTreeNode queuenew LinkedList();queue.add(root);while(!queue.isEmpty()){res.add(queue.peekLast().val);int currNumqueue.size();while(currNum!0){TreeNode temp queue.poll();if(temp.left!null){queue.add(temp.left);}if(temp.right!null){queue.add(temp.right);}currNum--;}}return res;}
}74.637. 二叉树的层平均值题目描述
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。第一版还是层次遍历
class Solution {public ListDouble averageOfLevels(TreeNode root) {ListDouble resnew ArrayList();if(rootnull){return res;}QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){int currNumqueue.size();// 不为double 加着加着就超范围了double sum0;for(int i0;icurrNum;i){TreeNode tempqueue.poll();sumtemp.val;if(temp.left!null){queue.offer(temp.left);}if(temp.right!null){queue.offer(temp.right);}}res.add(sum/currNum);}return res;}
}75.102. 二叉树的层序遍历题目描述
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。第一版这个最直接。。
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resnew ArrayList();if(rootnull){return res;}QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){int currNumqueue.size();ListInteger tempListnew ArrayList();for(int i0;icurrNum;i){TreeNode tempqueue.poll();tempList.add(temp.val);if(temp.left!null){queue.offer(temp.left);}if(temp.right!null){queue.offer(temp.right);}}res.add(tempList);}return res;}
}76.103. 二叉树的锯齿形层序遍历题目描述
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。第一版还是层次遍历第一层从左向右第二层从右向左。。。
class Solution {public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger resnew ArrayList();if(rootnull){return res;}boolean flagtrue;QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){int currNumqueue.size();ListInteger tempListnew ArrayList();for(int i0;icurrNum;i){TreeNode tempqueue.poll();if(flag)tempList.add(temp.val);elsetempList.add(0,temp.val);if(temp.left!null){queue.offer(temp.left);}if(temp.right!null){queue.offer(temp.right);}}flag!flag;res.add(tempList);}return res;}
}算是复习了一下二叉树的遍历写法递归和非递归的都有。。
第三十五天了加油早日跳槽
