云顶集团娱4118-4118ccm云顶集团
做最好的网站

Leetcode - Count Univalue Subtrees

日期:2019-10-08编辑作者:云顶集团

云顶集团注册送28,My code:

My code:

云顶集团4008网址,My code:

My code:

思路还是比较清楚的,三种艺术

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { int counter = 0; public int countUnivalSubtrees(TreeNode root) { if (root == null) { return 0; } helper; return counter; } private int helper(TreeNode root) { if (root.left == null && root.right == null) { counter++; return root.val; } else if (root.left == null) { int ret = helper(root.right); if (ret == -1) { return -1; } else if (ret != root.val) { return -1; } else { counter++; return ret; } } else if (root.right == null) { int ret = helper(root.left); if (ret == -1) { return -1; } else if (ret != root.val) { return -1; } else { counter++; return ret; } } else { int ret1 = helper(root.left); int ret2 = helper(root.right); if (ret1 == -1 || ret2 == -1) { return -1; } else { if (ret1 == root.val && ret2 == root.val) { counter++; return ret1; } else { return -1; } } } }}
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); if (root == null) { return ret; } Queue<TreeNode> q = new LinkedList<TreeNode>(); Queue<Integer> cols = new LinkedList<Integer>(); HashMap<Integer, List<Integer>> map = new HashMap<>(); q.offer; cols.offer; while (!q.isEmpty { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode curr = q.poll(); int col = cols.poll(); if (!map.containsKey { map.put(col, new ArrayList<Integer>; } map.get.add; if (curr.left != null) { q.offer(curr.left); cols.offer; } if (curr.right != null) { q.offer(curr.right); cols.offer; } } } int[] colArr = new int[map.keySet]; int counter = 0; for (Integer temp : map.keySet { colArr[counter++] = temp; } Arrays.sort; for (int i = 0; i < colArr.length; i++) { ret.add(map.get(colArr[i])); } return ret; }}
/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return null if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */public class NestedIterator implements Iterator<Integer> { Stack<Iterator<NestedInteger>> st = new Stack<>(); NestedInteger next; public NestedIterator(List<NestedInteger> nestedList) { st.push(nestedList.iterator; } @Override public Integer next() { return next == null ? null : next.getInteger(); } @Override public boolean hasNext() { while (!st.isEmpty { if (!st.peek().hasNext { st.pop(); } else { next = st.peek; if (next.isInteger { return true; } else { st.push(next.getList().iterator; } } } return false; }}/** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext] = i.next(); */
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if (root == null || p == null) { return null; } if (p.right != null) { TreeNode ret = p.right; while (ret.left != null) { ret = ret.left; } return ret; } TreeNode pre = null; TreeNode curr = root; while (curr != null) { if (curr.left == p) { return curr; } else if (curr.right == p) { return pre; } else if (curr.val < p.val) { curr = curr.right; } else { pre = curr; curr = curr.left; } } return null; }}

4008.com云顶集团,Union Find, BFS, DFS

post-order recursion

看了难题认为完全没思路。。。尽管知道要用hashmap后来看了答案才驾驭,能够给每种结点编八个列号,colcol能够是正数,也得以是负数,也足以是0,没提到,只是作为hashmap的三个key所以,假诺四个结点的号码是col,那么他的左孩子编号是col

那道难题未能自个儿做出来。看了答案后以为也很难想到。只不过真的很玄妙。

首先,那道标题自身竟然向来没做过,笔者代表很好奇。在本人脑海里,作者接近做过一些次了。最终变成小编不可能一边AC小编要好写出了这些iteration 的做法。然后关键点在哪个地方呢?在于,当 curr.val < p.val的时候,curr = curr.right, 但我们决不更新pre也正是说,当curr往左边走的时候,pre指针保留在原地。那是为了幸免,p是 curr那几个subtree的最右侧的结点,那么他的继承者就是pre,所以pre不能够动。只怕能够如此说,假如curr往右走,那么p的前者不必然会现出在那课右子树上,所以pre得做好希图假使往左走,那么p的子孙后代,一定在那棵左子树上!pre能够跟进假若curr往左侧走,那么就足以更新curr了。

Union Find采取的秘诀和找环大约。统一分类。然后看下最终有多少个例外的idMy code:

看了下答案,和本人相当多的思路,但写的更是简明,也可以有个别意况实际不是再细分了。

  • 1右孩子是 col + 1然后笔者一下懂事了.

reference:

假如p是curr的左孩子,那么curr正是后世。假诺p是curr的右孩子,那么pre正是后人

public class Solution { private int V = 0; private int[] id; private int[] sz; public int countComponents(int n, int[][] edges) { this.V = n; id = new int[V]; sz = new int[V]; for (int i = 0; i < V; i++) { id[i] = i; sz[i] = 1; } for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; union; union; } HashSet<Integer> set = new HashSet<Integer>(); for (int i = 0; i < n; i++) { set.add; } return set.size(); } private int find { if (id[u] == u) { return u; } else { int ret = find; id[u] = ret; return ret; } } private void union(int u, int v) { int left = find; int right = find; if (left == right) { return; } else { if (sz[left] > sz[right]) { sz[left] += sz[right]; id[right] = left; } else { sz[right] += sz[left]; id[left] = right; } } }}

Anyway, Good luck, Richardo! -- 09/06/2016

接下来利用多少个queue,三个存结点,八个存编号,两个始终同步,再加多level order,化解了这么些主题材料。

Leetcode - Count Univalue Subtrees。自家间接在想,假设list里面还应该有list,还只怕有list,还也可以有list,一千载难逢迭代进去,what will happen and what can we do?作者本来是想写一个dfs函数,但类似每回输出之后,原状态很难保存下去。那致使的标题是,下一回输出须要信任这几个原状态,如果原状态不能够保存,那么下叁次也无力回天输出。那是 stateful apiwe need to store the previous state to get the next state

相同的时候,一初步,就先判别p的右孩子是还是不是为空。倘使不是,那么她的后人,一定是右子树的最左侧结点。那便是iteration 做法的思量试的场馆

DFS,也和找环大概。顶层对各样结点DFS,若是 isVisited[i] 为false,就最早跑 recursion, counter++

而是留神看我代码的末梢有的。因为最后回来的结果,编号断定是从小到大的,而hashmap再次回到的keyset并无法确认保证有序性。所以本人先把富有的key放入二个数组,再排序,再从map收取相应的list,速度收到了十分大的熏陶。

接下来答案里面用到了五个数据结构:Stack + Iterator

接下来看答案看见了recursion做法,认为很抢眼,本人写了下。

My code:

本文由云顶集团娱4118发布于云顶集团,转载请注明出处:Leetcode - Count Univalue Subtrees

关键词:

ThreadPoolExecute源码剖判云顶集团:,ConcurrentLink

@Transactional参数表明 参数 说明 readOnly 是否是只读事务,true表示只读,false表示读写 timeout 事务超时秒数,默认值-1表...

详细>>

数据类型转换云顶集团:,写多少个好像jQuery的

前言 :近年来因为部分投机的政艺术学习停滞了一段时间,再捡起来时就可怜的别扭,十分大的打击了自己的学习热...

详细>>

您确实会写单例,java动态代理

来自: Android梦想特务职业职员队 作者: Aaron 主页: 有关Maven的下载配置就不做牵线。暗中同意Spring插件,maven插件...

详细>>

反射教程,快捷入门

JavaBean正是多个常备的java类 ,也堪当简单java对象--POJO(PlainOrdinary Java Object), 是Java程序设计中一种设计形式,是一...

详细>>