LeetCode 545. Boundary of Binary Tree 二叉树边界

Astrian 发布于2019-08-16 13:31 / 1665人阅读

摘要：二叉树边界题意高频题，必须熟练掌握。逆时针打印二叉树边界。解题思路根据观察，我们发现当为左边界时，也是左边界当为左边界时，为空，则也可以左边界。先加入左边，加入，然后得到两个子树加入，最后加入右边界。

LeetCode 545. Boundary of Binary Tree 二叉树边界
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
Input:

Ouput:
[1, 3, 4, 2]

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

Input:

    ____1_____
   /          
  2            3
 /           / 
4   5        6   
   /       / 
  7   8    9  10

Ouput:
[1,2,4,7,8,9,10,6,3]

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].

题意: 高频题，必须熟练掌握。逆时针打印二叉树边界。

解题思路：
根据观察，我们发现

当node为leftBound左边界时，node.left也是左边界

当node为leftBound左边界时，node.left为空，则node.right也可以leftBound左边界。

Bottom的所有都要加入其中。

rightBound也是如此。

我们可以循环调用dfs，初始化leftBound和rightBound两个boolean参数，一层层判断。先加入左边，加入bottom，然后得到两个子树加入，最后加入右边界。

代码如下：

/**
    * node.left is left bound if node is left bound;
    * node.right could also be left bound if node is left bound && node has no left child;
    * Same applys for right bound;
    * if node is left bound, add it before 2 child - pre order;
    * if node is right bound, add it after 2 child - post order;
    * A leaf node that is neither left or right bound belongs to the bottom line;
    */
    public List boundaryOfBinaryTree(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;
        res.add(root.val);
        getBounds(root.left, res, true, false);
        getBounds(root.right, res, false, true);
        return res;
    }
    public void getBounds(TreeNode node, List res, boolean leftBound, boolean rightBound) {
        if (node == null) return;
        if (leftBound) {
            res.add(node.val);
        }
        //add bottom
        if(!leftBound && !rightBound && node.left == null && node.right == null) {
            res.add(node.val);
        }
        getBounds(node.left, res, leftBound, rightBound && node.right == null);
        getBounds(node.right, res, leftBound && node.left == null, rightBound);
        if (rightBound) {
            res.add(node.val);
        }
        
        
    }

GPU云服务器云服务器 binary-tree binary-search-tree 二叉树 python二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71881.html

[LeetCode] 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 no...

newtrek 2019-08-16 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 104 Maximum Depth of Binary Tree 二叉树最大深度

LeetCode 104 Maximum Depth of Binary Tree难度：Easy 题目描述：找到一颗二叉树的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...

PiscesYE 2019-08-16 13:28 评论0 收藏0
LeetCode 110 Balanced Binary Tree 平衡二叉树

摘要：题意判断一颗二叉树是否是平衡二叉树，平衡二叉树的定义为，每个节点的左右子树深度相差小于这是和求最大深度的结合在一起，可以考虑写个函数找到拿到左右子树的深度，然后递归调用函数判断左右子树是否也是平衡的，得到最终的结果。 LeetCode 110 Balanced Binary Tree Given a binary tree, determine if it is height-bala...

anquan 2019-08-16 13:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0