[LeetCode] 199. Binary Tree Right Side View

KunMinX 发布于2019-08-16 13:48 / 2100人阅读

Problem

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   
2     3         <---
      
  5     4       <---

Solution - BFS

class Solution {
    public List rightSideView(TreeNode root) {
        //save into stack in level order
        List res = new ArrayList<>();
        if (root == null) return res;
        Deque queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                if (i == size-1) res.add(cur.val);
            }
        }
        return res;
    }
}

Solution - DFS

class Solution {
    public List rightSideView(TreeNode root) {
        List res = new ArrayList<>();
        if (root == null) return res;
        dfs(root, 0, res);
        return res;
    }
    private void dfs(TreeNode root, int level, List res) {
        if (root == null) return;
        if (res.size() == level) res.add(root.val);
        dfs(root.right, level+1, res);
        dfs(root.left, level+1, res);
    }
}

海外云主机私有云 binary-tree binary-search-tree Side right

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

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

199. Binary Tree Right Side View

摘要：问题解答核心思想是每一层只取一个结点，所以的大小与高度是一样的。问题：Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example:Giv...

YJNldm 2019-08-14 14:13 评论0 收藏0
[Leetcode] Binary Tree Right Side View 二叉树右视图

摘要：代码层序遍历复杂度时间空间对于二叉树思路我们同样可以借用层序遍历的思路，只要每次把这一层的最后一个元素取出来就行了，具体代码参见中的 Binary Tree Right Side View Given a binary tree, imagine yourself standing on the right side of it, return the values of the n...

hearaway 2019-08-14 12:25 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
LeetCode 606. Construct String from Binary Tree 二叉

摘要：题意从一颗二叉树转为带括号的字符串。这题是的姊妹题型，该题目的解法在这里解法。 LeetCode 606. Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder t...

mikyou 2019-08-16 13:31 评论0 收藏0
LeetCode 156 Binary Tree Upside Down 上下翻转二叉树

摘要：翻转以后如下解题思路翻转的形式一开始不是很清楚，但是里面的高票答案给了一个很好的解释。看例子，树的左边最深的底层是，是新的。对于每个，将链接右孩子的指针去掉，将变为当前左孩子的，成为左孩子的。递归的写法递归调用得到新的，并且沿途改变结构。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

Loong_T 2019-08-16 13:28 评论0 收藏0