查找binary tree中有多少个uni－valued subtree - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 查找binary tree中有多少个uni－valued subtree

相关主题
● 问一道google面经	● careercup 150 4.1 balanced tree 有错？
● Flatten Binary Tree to Linked List的recursive解法	● 贡献Google 电面面经
● 请问LC上一道题：Validate BST	● 树中序遍历，要求左子树用递归，右子树用iteration
● Unique Binary Search Trees II的复杂度怎么算啊？多谢！	● largest bst 解法不理解的地方
● find treenode with two indegrees	● 贴个自己的答案：Binary Tree Max Path Sum
● 请教这么一个题：BST maximum sum path	● unique binary tree 2 (leetcode)
● Uni_value subtree problem	● leetcode一题，自己编译没问题，leetcode总是编译出错。请高手看看
● 今天面的太惨了....	● 有没有人同觉得Recover Binary Search Tree的solution using O(n) space并不是那么straight forward么？

相关话题的讨论汇总
话题: treenode话题: helper话题: null话题: return话题: isuni

进入JobHunting版参与讨论

1

(共1页)

T******7 发帖数: 1419	1 2. 查找binary tree中有多少个uni－valued subtree，uni－valued tree的定义是所有其中node value值一样。这题有什么好思路么？求一点指点謝謝
k****r 发帖数: 807	2 是recursive吗？看左边也是uni，右边也是uni，同时他们的val都喝root的一样，就整个夜市uni uni的定义是null，or 单个val的节点。
T******7 发帖数: 1419	3 写了一个很丑的code. 求拍。 public class uniValueTree { public int countUniTree(TreeNode root){ if(root.left == null && root.right == null) return 1; return helper(root); } private int helper(TreeNode node){ if(node.left == null && node.right == null){ return 1; } if(node.left == null){ if(isUni(node.right)){ if(node.val == node.right.val){ return 1 + helper(node.right); }else{ return helper(node.right); } } } else if(node.right == null){ if(isUni(node.left)){ if(node.val == node.left.val){ return 1 + helper(node.left); } else { return helper(node.left); } } } else if(isUni(node.left) && isUni(node.right) && (node.val == node. left.val) && (node.val == node.right.val)){ return 1 + helper(node.left) + helper(node.right); } return helper(node.left) + helper(node.right); } private boolean isUni(TreeNode node){ return (node != null) && (node.left == null && node.right == null) ; } public static void main(String[] args){ TreeNode root = new TreeNode(2); root.left = new TreeNode(1); root.left.left = new TreeNode(1); root.left.right = new TreeNode(1); root.right = new TreeNode(3); uniValueTree ut = new uniValueTree(); int ret = ut.countUniTree(root); System.out.println(ret); } // 2 // / \ // 1 3 // / \ // 1 1 // }

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 有没有人同觉得Recover Binary Search Tree的solution using O(n) space并不是那么straight forward么？	● find treenode with two indegrees
● Construct Binary Tree from Preorder and Inorder Traversal算法复杂度？	● 请教这么一个题：BST maximum sum path
● 请教一道g算法题	● Uni_value subtree problem
● 请教两道F面试题的follow up	● 今天面的太惨了....
● 问一道google面经	● careercup 150 4.1 balanced tree 有错？
● Flatten Binary Tree to Linked List的recursive解法	● 贡献Google 电面面经
● 请问LC上一道题：Validate BST	● 树中序遍历，要求左子树用递归，右子树用iteration
● Unique Binary Search Trees II的复杂度怎么算啊？多谢！	● largest bst 解法不理解的地方

相关话题的讨论汇总
话题: treenode话题: helper话题: null话题: return话题: isuni

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)