# LeetCode Weekly Contest 25

## 赛题

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

### My first solution(28ms)

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

//添加根节点

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

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

//对右边界直接进行遍历
rightDfs(root.right, right);

for (int i = 1; i < right.size(); 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);
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) {
}

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);
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);
curr = curr.left;
} else {
TreeNode node = stack.pop();
curr = node.right;
if (curr == null) {
break;
}
}
}
}```

```if (curr == null) {
break;
}```

```private void leftDFS(TreeNode root, LinkedList<Integer> left) {

//边界条件
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);
}
}```

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

#### 叶子节点遍历

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

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

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);
curr = curr.right;
} else {
TreeNode node = stack.pop();
curr = node.left;
if (curr == null) {
break;
}
}
}
}```

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

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<>();

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

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

rightDFS(root.right, right);

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

return left;
}

private void leftDFS(TreeNode root, LinkedList<Integer> left) {

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;

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) {
}

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

0 条评论

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

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

• ### LeetCode Weekly Contest 24 之 538.Convert BST to Greater Tree

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

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

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

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

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

• ### 浅说深度学习

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

• ### Python素材下载爬虫，ui素材下载爬取采集源码

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