298. Binary Tree Longest Consecutive Sequence
先序遍历,根左右。如果该节点的 value == 父节点value + 1, 则长度+1; 否则重置为1。
class Solution { private int res = 0; public int longestConsecutive(TreeNode root) { if(root == null) return 0; dfs(root, root.val, 0); return res; } private void dfs(TreeNode root, int v, int out){ if(root == null) return; if(root.val == v + 1){ out++; }else{ out = 1; } res = Math.max(res, out); dfs(root.left, root.val, out); dfs(root.right, root.val, out); } }
250. Count Univalue Subtrees
后序遍历,左右根。
如果节点为叶子节点则 count++,并验证该节点是否与父节点的值相同,是则为true。如果节点和左右子树返回值都是true,则count++。
1.叶节点也都相同,count++。
2.对于当前遍历到的节点,如果对其左右子节点分别递归调用函数,返回均为true的话,那么说明当前节点的值和左右子树的值都相同,那么又多了一棵树,所以结果自增1
class Solution { private int count; public int countUnivalSubtrees(TreeNode root) { count = 0; helper(root, Integer.MAX_VALUE); return count; } private boolean helper(TreeNode root, int v){ if(root == null) return true; boolean left = helper(root.left, root.val); boolean right = helper(root.right, root.val); if(left && right){ count++; return root.val == v; } return false; } }
366. Find Leaves of Binary Tree
一层一层剥离当前树的所有叶子节点。叶子节点高度设为0,所以 res.size( )的大小 == 当前层数 + 1。
每一个节点从左子节点和右子节点分开走可以得到两个深度,由于成为叶节点的条件是左右子节点都为空,所以我们取左右子节点中较大值加1为当前节点的深度值,知道了深度值就可以将节点值加入到结果res中的正确位置了。加入root.val时要remove该叶子节点 root = null。
class Solution { public List<List<Integer>> findLeaves(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); height(root, res); return res; } private int height(TreeNode root, List<List<Integer>> res){ if(root == null) return -1; int level = Math.max(height(root.left, res), height(root.right, res)) + 1; if(res.size() < level + 1){ res.add(new ArrayList<>()); } res.get(level).add(root.val); root = null; return level; } }