【LC刷题系列】【持续更新】二叉树问题

30次阅读
没有评论

遍历问题:

  • 二叉树的遍历分为DFS和BFS,DFS分为前序遍历 中序遍历 后序遍历,通常实现是递归,但是有溢出的可能,所以非递归实现中 前序遍历一般使用stack实现,利用其特性实现,注意 前序遍历的特点是中 左 右 ,所以入栈顺序要先右再左。 前序遍历:

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

    中序遍历::把树看作一个个“撇”,把每个撇逐个入站,然后弹出时候判断是否有右子节点,如果有的话,就把右子节点入展,下一个弹出,这样是根据二叉树中序遍历的特点归纳出来的方法。即:左中右的顺序,左和中都在撇上,右作为单独判断

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

    后序遍历:

    
    
**层序遍历(DFS):** 使用队列 先入先出 可以使用标志位 实现监控每一层的结束
```[java]
    public List<Integer> zhongxu(TreeNode root) {
        List<Integer> list = new ArrayList<>();
            if(root!=null){
                Queue<Integer> queue =new LinkedList<>();
                queue.add(root);
                while(!queue.isEmpty()){
                    root = queue.poll();
                    list.add(root.val);
                    if(root.left!=null){
                        queue.add(root.left);
                    }
                    if(root.right!=null){
                        queue.add(root.right);
                    }
                }

102. 二叉树的层序遍历 严格意义上的层序遍历呢 每层要在不同的数组。 是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时候我们可以利用linkedHashMap,维护一个以 对应节点值组成的数组 为键,level为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可

    /**
     * 层序遍历 一层一个list
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root != null) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            LinkedHashMap<TreeNode, Integer> levelMap = new LinkedHashMap<>();
            levelMap.put(root, 1);
            while (!queue.isEmpty()) {
                root = queue.poll();

                if (root.left != null) {
                    queue.add(root.left);
                    levelMap.put(root.left, levelMap.get(root) + 1);
                }
                if (root.right != null) {
                    queue.add(root.right);
                    levelMap.put(root.right, levelMap.get(root) + 1);
                }
            }
            return dothings(levelMap);
        }
        return new ArrayList<>();
    }
    /**
     * 处理map 转为需要的形式
     * @param root
     * @return
     */
    public List<List<Integer>> dothings(LinkedHashMap<TreeNode,Integer> levelMap){
        List<List<Integer>> result = new ArrayList<>();
        int lastLevel=0;
        Iterator<Map.Entry<TreeNode, Integer>> iterator = levelMap.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<TreeNode, Integer> next = iterator.next();
            if (lastLevel!=next.getValue()){
                List<Integer> thisLevel = new ArrayList<>();
                thisLevel.add(next.getKey().val);
                result.add(thisLevel);
                lastLevel = next.getValue();
            }else {
                result.get(result.size()-1).add(next.getKey().val);
            }

        }
        return result;
    }

待改进:输出的map可以不是这个形式,map转答案的方法笨重了些,而且严重依赖于linkedHashMap有序的特点,但是没想好用什么方式输出节点和他们的层级关系 转list会方便些。


622.二叉树的最大宽度:我下面的题解是针对null节点不计入宽度的规则实现的,也是用map记录每个节点和它对应的层级,但是想不出怎么计算包含null节点的最大宽度。待解决

    public int widthOfBinaryTree(TreeNode root) {
        if(root != null){
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            Map<TreeNode,Integer> levelMap =new HashMap<>();
            levelMap.put(root,1);
            Integer focusOn = 1;//现在在处理哪一层
            Integer thisWidth = 0;//当前层宽度 出来时候统计
            int max = 0;//用来在层与层之间比较大小使用的值
            while(!queue.isEmpty()){
                root = queue.poll();

                if(root.left!=null){
                    queue.add(root.left);
                    levelMap.put(root.left,levelMap.get(root)+1);//下一层入map ,层级+1
                }
                if(root.right!=null){
                    queue.add(root.right);
                    levelMap.put(root.right,levelMap.get(root)+1);
                }
                if(focusOn.equals(levelMap.get(root))){
                    thisWidth++;//你确实是这层的人 宽度++
                }else{
                    //如果进入else 证明按层序遍历的下一层的节点出来了 00后诞生
                    focusOn++;//看下一层
                    max = Math.max(max,thisWidth);//和上一届最大值相比
                    thisWidth=1;//宽度给回初始值 因为如果有下层 肯定有节点 最小就是1

                }
            }
            max = Math.max(max,thisWidth);
            return max;
        }
        return 0;
    }
评论(没有评论)