<Tree> 298 250 366 199（高频） 98(高频)

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;

    }

}

199. Binary Tree Right Side View

求每一层最右边的节点

先序遍历中序遍历后序遍历都可，只要保证右侧节点的添加在左侧添加之后。

每当开始新一层节点的遍历之前，先把新一层最后一个节点值存到结果中

class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> res = new ArrayList<>();

        HashMap<Integer, Integer> map = new HashMap<>();

        int depth = 1;

        dfs(root, depth, map);

        //map --> List<Integer> list

        depth = 1;

        while(map.containsKey(depth)){

            res.add(map.get(depth));

            depth++;

        }

        return res;

    }

    private void dfs(TreeNode root, int depth, Map<Integer, Integer> map){

        //Exit

        if(root == null) return;

        //traverse

        map.put(depth, root.val); // do not have to be preorder

        dfs(root.left, depth + 1, map);

        dfs(root.right, depth + 1, map);

    }

}

98. Validate Binary Search Tree

测试用例中可能有超过Integer.MAX_VALUE的值。故用Long.MAX_VALUE

class Solution {

    public boolean isValidBST(TreeNode root) {

        if(root == null) return true;

        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }

    private boolean valid(TreeNode root, long low, long high){

        if(root == null) return true;

        if(root.val <= low || root.val >= high) return false;

        return valid(root.left, low,  Math.min(root.val, high)) && valid(root.right, Math.max(low, root.val), high);

    }

}

巴特西

<Tree> 298 250 366 199（高频） 98(高频)

最新文章

热门文章