专栏首页机器学习入门LeetCode Weekly Contest 25 之 545.Boundary of Binary Tree

LeetCode Weekly Contest 25 之 545.Boundary of Binary Tree

LeetCode Weekly Contest 25

赛题

本次周赛主要分为以下4道题:

  • 507 Perfect Number (3分)
  • 537 Complex Number Multiplication (6分)
  • 545 boundary of Binary Tree (8分)
  • 546 Remove Boxes (9分)

545 Boundary of Binary Tree

Problem:

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes. Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees. The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node. The right-most node is also defined by the same way with left and right exchanged.

Example 1

Explanation:

  • The root doesn’t have left subtree, so the root itself is left boundary.
  • The leaves are node 3 and 4.
  • The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
  • So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Example 2

Explanation:

  • The left boundary are node 1,2,4. (4 is the left-most node according to definition)
  • The leaves are node 4,7,8,9,10.
  • The right boundary are node 1,3,6,10. (10 is the right-most node).
  • So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

这道题考的是树的各种遍历,还是比较难的,早上刚复习了树的三种迭代遍历,否则让我用递归的方法还真的搞不定。题目的大致意思是说,先遍历根的【左边界】,并且输出,然后再遍历每个叶子节点,并输出,最后遍历根的【右边界】最后输出,方向就好像是个anti-clockwise。典型的给你思路,考你对树遍历的理解程度。

My first solution(28ms)

public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        if (root == null)
            return new ArrayList<>();

        //添加根节点
        LinkedList<Integer> left = new LinkedList<>();
        left.add(root.val);

        //如果有左边界,则进行左边界遍历
        if (root.left != null) {
            leftDfs(root.left, left);
            left.remove(left.size() - 1);
        }

        //如果有左边界和右边界,则进行叶子节点遍历
        if (root.left != null || root.right != null)
            leaveDfs(root, left);

        //对右边界直接进行遍历
        LinkedList<Integer> right = new LinkedList<>();
        rightDfs(root.right, right);

        for (int i = 1; i < right.size(); i++) {
            left.add(right.get(i));
        }

        return left;
    }

    private void leftDfs(TreeNode root, LinkedList<Integer> left) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {

            if (curr != null) {
                stack.push(curr);
                left.add(curr.val);
                curr = curr.left;
            } else {
                TreeNode node = stack.pop();
                curr = node.right;
                if (curr == null) {
                    break;
                }
            }
        }

    }

    private void leaveDfs(TreeNode root, LinkedList<Integer> leaves) {
        if (root == null)
            return;

        if (root.left == null && root.right == null) {
            leaves.add(root.val);
        }

        leaveDfs(root.left, leaves);
        leaveDfs(root.right, leaves);
    }

    private void rightDfs(TreeNode root, LinkedList<Integer> right) {

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                right.addFirst(curr.val);
                curr = curr.right;
            } else {
                TreeNode node = stack.pop();
                curr = node.left;
                if (curr == null) {
                    break;
                }
            }
        }
    }

这里有很多细节问题,需要实际写遍代码才能感受得到,我不去说明如何把这三部分的遍历结果拼接在一块的,而是单独分析这三部分遍历是如何实现的,并看看还有没有优化的地方。

左边界遍历

迭代版本

private void leftDfs(TreeNode root, LinkedList<Integer> left) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {

            if (curr != null) {
                stack.push(curr);
                left.add(curr.val);
                curr = curr.left;
            } else {
                TreeNode node = stack.pop();
                curr = node.right;
                if (curr == null) {
                    break;
                }
            }
        }
    }

这是树先序的迭代版本,主要区别在于else当中的:

if (curr == null) {
    break;
}

左边界的停止条件是当前节点的左节点为null,以及右节点也为null,所以在当curr.left == null时,它会进入else循环,并且弹出curr节点,此时,我们只需要判断curr.right == null即可,此时为一个叶子节点自然可以跳出循环了。

递归版本

private void leftDFS(TreeNode root, LinkedList<Integer> left) {
        left.add(root.val);

        //边界条件
        if(root.left == null && root.right == null) return;

        if(root.left != null){ //约束条件1
            leftDFS(root.left, left);
        }

        else if(root.right != null){ //约束条件2
            leftDFS(root.right,left);
        }
    }

使用递归的话,则首先需要考虑递归的终止条件,很显然,只有当我访问的当前节点的左节点和右节点均为null时递归就可以结束了,所以有了边界条件。这里的另外两个细节在于对递归的约束:

  • 约束条件1:如果当前节点的左节点存在,则递归寻找,没有则跳至它的右节点。
  • 约束条件2:如果右节点不存在,则不再需要递归,整个函数返回,如果存在,则开始下一轮的边界寻找。

可以看到leftDFS()传入的节点root不可能为空,所以不需要判断。

叶子节点遍历

private void leaveDfs(TreeNode root, LinkedList<Integer> leaves) {
        if (root == null)
            return;

        //挑选叶子节点
        if (root.left == null && root.right == null) {
            leaves.add(root.val);
        }

        leaveDfs(root.left, leaves);
        leaveDfs(root.right, leaves);
    }

它的思路很简单,一个先序遍历,只需要把叶子节点挑出来,放在leaves集合当中即可。

右边界遍历

迭代版本

private void rightDfs(TreeNode root, LinkedList<Integer> right) {

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                right.addFirst(curr.val);
                curr = curr.right;
            } else {
                TreeNode node = stack.pop();
                curr = node.left;
                if (curr == null) {
                    break;
                }
            }
        }
    }

如果理解了左边界的遍历,那么右边界的遍历也很容易理解,无非是把curr的走向改一改,从右边开始咯,所以有curr = curr.right,当然还需要注意一个细节,LinkedList的使用,由题目的意思,右边界的遍历应该是从下而上的,所以我们在加入链表时,进行头插。

递归版本

private void rightDFS(TreeNode root, LinkedList<Integer> right) {
        if(root == null) return;

        right.addFirst(root.val);

        if(root.left == null && root.right == null) return;

        if(root.right != null){
            rightDFS(root.right, right);
        }

        else if(root.left != null){
            rightDFS(root.left,right);
        }
    }

和左边界遍历一模一样,不解释了。所以我们有一份纯净版的递归实现。

My second solution(15ms)

public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        if (root == null)
            return new ArrayList<>();

        LinkedList<Integer> left = new LinkedList<>();
        left.add(root.val);

        if (root.left != null) {
            leftDFS(root.left, left);
            left.remove(left.size() - 1);
        }

        leavesDFS(root.left, left);
        leavesDFS(root.right, left);

        LinkedList<Integer> right = new LinkedList<>();
        rightDFS(root.right, right);

        for (int i = 1; i < right.size(); i++) {
            left.add(right.get(i));
        }

        return left;
    }



    private void leftDFS(TreeNode root, LinkedList<Integer> left) {
        left.add(root.val);

        if (root.left == null && root.right == null)
            return;

        if (root.left != null) {
            leftDFS(root.left, left);
        } else if (root.right != null) {
            leftDFS(root.right, left);
        }
    }

    private void rightDFS(TreeNode root, LinkedList<Integer> right) {
        if (root == null)
            return;

        right.addFirst(root.val);

        if (root.left == null && root.right == null)
            return;

        if (root.right != null) {
            rightDFS(root.right, right);
        }

        else if (root.left != null) {
            rightDFS(root.left, right);
        }
    }

    private void leavesDFS(TreeNode root, LinkedList<Integer> leaves) {
        if (root == null)
            return;

        if (root.left == null && root.right == null) {
            leaves.add(root.val);
        }

        leavesDFS(root.left, leaves);
        leavesDFS(root.right, leaves);
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode Weekly Contest 24 之 543. Diameter of Binary Tree

    第一反映是递归,假设root的左子树以及右子树的diameterOfBinaryTree已经求解出来,那么我们只需要判断一种情况即可,即diameterOfBi...

    用户1147447
  • Minimum Distance Between BST Nodes

    用户1147447
  • LeetCode Weekly Contest 24 之 538.Convert BST to Greater Tree

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • RocketMQ分布式消息中间件-Centos7安装运行

    消息队列作为高并发系统的核心组件之一,能够帮助业务系统解构提升开发效率和系统稳定性。最近公司的项目也是用上了RocketMQ,所以这里记录一下RocketMQ环...

    奋斗蒙
  • 008.Linux文件目录管理命令基础

    CoderJed
  • Centos7下ELK+Redis日志分析平台的集群环境部署记录

    之前的文档介绍了ELK架构的基础知识(推荐参考下http://blog.oldboyedu.com/elk/),日志集中分析系统的实施方案: - ELK+Red...

    洗尽了浮华
  • 浅说深度学习:核心概念

    用户1737318
  • 浅说深度学习

    在机器学习中,我们(1)读取数据,(2)训练模型,(3)使用模型对新数据做预测。训练可以看作是当模型拿到新数据的时候、逐步学习一个的过程。在每一步,模型做出预测...

    华章科技
  • 剑指offer(3)——二维数组中的查找

    说故事的五公子
  • Python素材下载爬虫,ui素材下载爬取采集源码

    Uimaker是为UI设计师提供学UI设计的专业UI平台,拥有UI教程、UI素材、ICON、图标设计UI、手机UI、ui设计师招聘、软件界面设计、后台界面、后台...

    二爷

扫码关注云+社区

领取腾讯云代金券