<Tree> 298 250 366

扫码查看

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;
    }
}
12-18 06:20
查看更多