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