[LeetCode] 199. Binary Tree Right Side View

KunMinX 發布于2019-08-16 13:48 / 2189人閱讀

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

云服務器 GPU云服務器 binary-tree binary-search-tree Side right

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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