Tree

538. Convert BST to Greater Tree

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
5
/
2 13

Output: The root of a Greater Tree like this:
18
/
20 13

题意就是每个节点的值是本身加上所有比它大的节点的值，所有最右边是所有节点的和20。BST一定要想到inorder遍历。这道题反过来in order遍历。

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        // inverse inorder traversal
        // right root left
        if (root == null) {
            return null;
        }
        convertBST(root.right);
        root.val = root.val + sum;
        sum = root.val;
        convertBST(root.left);
        
        return root;
    }
}

315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

有两个点。一是找5以后比5小的数，要想到可以从后往前找。二是想到构建一个二叉树来解题，node里再存一个count记录左子树的个数。有几个细节没想清楚，一是如果出现相等的数字怎么办。二是把结果的list当参数传进去。最后学习如何手写一个BST。

class Solution {
    /**
    1. add into tree reversely
    2. how to handle equally
    */
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        // construct a binary search tree
        BST bst = new BST(); 
        // add from right to left
        for (int i = nums.length - 1; i >= 0; i--) {
            bst.insert(nums[i], res);
        }
        Collections.reverse(res);

        return res;
    }
    
    class TreeNode {
    TreeNode left, right;
    int count; // number of nodes in the left substree
    int val; // root's value
    public TreeNode(int val) {
        this.count = 0;
        this.left = this.right = null;
        this.val = val;
        }
    }
    
    class BST {
        TreeNode root;
        public BST () {
            root = null;
        }

        public void insert (int num, List<Integer> res) {
            root = insert(root, num, 0, res);
        }
        
        private TreeNode insert(TreeNode node, int val, int sum, List<Integer> res) {
            if (node == null) {
                node = new TreeNode(val);
                res.add(sum);
                return node;
            }
            if (node.val > val) {
                node.count++;
                node.left = insert(node.left, val, sum, res);
            } else {
                node.right = insert(node.right, val, sum + node.count + (node.val == val ? 0 : 1), res);
            }
            return node;
        }
    }
}

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,
1 <---
/
2 3 <---
\
5 4 <---
You should return [1, 3, 4].

用level order做。需要注意的是一开始没有考虑到这种情况。
1
/
2 3
\
5

655. Print Binary Tree

Input:
1
/
2 3

4
Output:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]

数组的长度是树的宽度，个数是树的高度，用分治做，递归函数有哪些参数需要注意。剩下就是细节，Math函数返回double，list如何在指定位置插入。最好把结果的二维list初始化好 这样更方便。

class Solution {
    public List<List<String>> printTree(TreeNode root) {
        // get the height and width of the given tree
        int height = getHeight(root);
        int width = (int) Math.pow(2, height) - 1; // pow return double 
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < height; i++) {
            List<String> list = new ArrayList<>();
            for (int j = 0; j < width; j++) {
                list.add("");
            }
            res.add(list);
        }
        // fill the list of each level 
        helper(root, res, 0, 0, width - 1);
        return res;
    }
    // helper function, fill list
    public void helper(TreeNode root, List<List<String>> res, int level, int left, int right) {
        if (root == null) {
            return;
        }
        int mid = (left + right) / 2;
        res.get(level).set(mid, String.valueOf(root.val));
        helper(root.left, res, level + 1, left, mid - 1);
        helper(root.right, res, level + 1, mid + 1, right);
        
    }
    
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}

遍历

  • 前序
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> preorder = new ArrayList<Integer>();
        
        if (root == null) {
            return preorder;
        }
        
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            preorder.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        
        return preorder;
    }
  • Level Order
  • In Order

543. Diameter of Binary Tree

Given a binary tree
1
/
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

用MaxDepth做

173. Binary Search Tree Iterator

Implement an iterator of a BST, next() and hasNext()

BST的inorder traversal是有序的，关键是弹出leftmost之后如何能找到父亲节点，想到用stack
关键是知道BST的inorder和使用stack保存父亲节点

98. Validate Binary Search Tree

如题

一种是分治，分到左右子树。把当前value传到左子树做最大值，传到右子树做最小值，如果当前值小于最大值，大于最小值，而且左右子树都true，那么返回true。感觉跟正常的分治有点区别。
BST要想到inorder遍历，用stack记录每个左节点，到了leftmost之后开始pop，存在右节点就处理右节点，没有就再pop获取其父亲。然后pop出来，再处理右节点

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
        
    }
    return list;
}

314. Binary Tree Vertical Order Traversal

  • 观察得知用level order遍历
  • 每个node还需要有一个offset信息 （root是0，左孩子是-1，右孩子是1）想到用另一个queue和level order的queue同步更新
  • Keep track of leftmost and rightmost，最后从hashmap拿数据时候用
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // column - points
        Map<Integer, List<Integer>> map = new HashMap<>();
        // traverse the tree
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> c = new LinkedList<>();
        q.offer(root);
        c.offer(0);
        // keep track of leftmost and rightmost
        int left = 0, right = 0;
        
        while(!q.isEmpty()) {
            int column = c.poll();
            TreeNode cur = q.poll();
            if (map.containsKey(column)) {
                map.get(column).add(cur.val);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(cur.val);
                map.put(column, list);
            }
            if (cur.left != null) {
                q.offer(cur.left);
                c.offer(column - 1);
                left = Math.min(left, column - 1);
            }
            if (cur.right != null) {
                q.offer(cur.right);
                c.offer(column + 1);
                right = Math.max(right, column + 1);
            }
        }
        for (int i = left; i <= right; i++) {
            res.add(map.get(i));
        }
        return res;
        
    }

652. Find Duplicate Subtrees

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

递归的序列化每个子树

class Solution {
    // serialize the tree
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, Integer> map = new HashMap<>(); // store every serialized subtree, if duplicate store it into res
        List<TreeNode> list = new ArrayList<>();
        serialize(root, map, list);
        return list;
    }
    public String serialize(TreeNode node, Map<String, Integer> map, List<TreeNode> list) {
        if (node == null) {
            return "#";
        }
        String key = node.val + "," + serialize(node.left, map, list) + "," + serialize(node.right, map, list);
        map.put(key, map.getOrDefault(key, 0) + 1);
        if (map.get(key) == 2) {
            list.add(node);
        }
        return key;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • Tree
    总结类型： 完全子树（#222） BST（左右子树值的性质，注意不仅要满足parent-child relatio...
    __小赤佬__阅读 3,991评论 0赞 0
  • Leetcode--Tree
    94. Binary Tree Inorder Traversal 中序 inorder：左节点－>根节点－>右节...
    Morphiaaa阅读 3,831评论 0赞 0
  • 用户选择数据提交后台
    做个简单练习，题目关于点菜。要求用户注册登录之后，来到点菜页面，点菜页面数据从后台数据库获取后页面渲染出来。用户选...
    2010jing阅读 3,978评论 4赞 4
  • 使用xshell连接virtualbox里面的CentOS
    什么是xshell？ xshell是一个终端模拟软件，简单来说我们可以通过xshell连接上服务器上的linux操...
    ppmoon阅读 7,983评论 0赞 50
  • 我的心里只有你
    第一次邂逅，你还是个少年 我和你是同座，你笑的样子真的吸引了我 于是…… 午餐时帮你打扫 作业帮你记好 考试时一起...
    夙醉银阅读 1,315评论 0赞 0

友情链接更多精彩内容