资讯专栏INFORMATION COLUMN

[LeetCode] 545. Boundary of Binary Tree

newtrek / 1056人阅读

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

Input:
  1
   
    2
   / 
  3   4

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

Solution
class Solution {
    public List boundaryOfBinaryTree(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;
        res.add(root.val);
        helper(root.left, true, false, res);
        helper(root.right, false, true, res);
        return res;
    }
    private void helper(TreeNode root, boolean leftBound, boolean rightBound, List res) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            res.add(root.val);
            return;
        }
        if (leftBound) res.add(root.val);
        helper(root.left, leftBound, root.right == null && rightBound, res);
        helper(root.right, root.left == null && leftBound, rightBound, res);
        if (rightBound) res.add(root.val);
    }
}

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

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

相关文章

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

    摘要:二叉树边界题意高频题,必须熟练掌握。逆时针打印二叉树边界。解题思路根据观察,我们发现当为左边界时,也是左边界当为左边界时,为空,则也可以左边界。先加入左边,加入,然后得到两个子树加入,最后加入右边界。 LeetCode 545. Boundary of Binary Tree 二叉树边界Given a binary tree, return the values of its boun...

    Astrian 评论0 收藏0
  • LeetCode 536. Construct Binary Tree from String 从带

    摘要:题意从一个带括号的字符串,构建一颗二叉树。其中当而时,展示为一个空的括号。同时要考虑负数的情况,所以在取数字的时候,必须注意所在位置。遇到则从栈中出元素。最后中的元素就是,返回栈顶元素即可。 LeetCode 536. Construct Binary Tree from String You need to construct a binary tree from a string ...

    tabalt 评论0 收藏0
  • [LeetCode] 543. Diameter of Binary Tree

    Problem Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may ...

    Y3G 评论0 收藏0
  • 前端 | 每天一个 LeetCode

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

    张汉庆 评论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 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<