Welcome to Subscribe On Youtube
-
import java.util.LinkedList; import java.util.Queue; /** Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: 2 / \ 1 3 Output: 1 Example 2: Input: 1 / \ 2 3 / / \ 4 5 6 / 7 Output: 7 Note: You may assume the tree (i.e., the given root node) is not NULL. */ public class Find_Bottom_Left_Tree_Value { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { // bfs if (root == null) { return -1; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int currentLevelCount = 1; int nextLevelCount = 0; int result = root.val; boolean isLevelLeftMost = false; while (!q.isEmpty()) { TreeNode current = q.poll(); currentLevelCount--; // check leftmost if (isLevelLeftMost) { result = current.val; isLevelLeftMost = false; } if (current.left != null) { q.offer(current.left); nextLevelCount++; } if (current.right != null) { q.offer(current.right); nextLevelCount++; } if (currentLevelCount == 0) { currentLevelCount = nextLevelCount; nextLevelCount = 0; // mark next node of queue is the possible result isLevelLeftMost = true; } } return result; } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> q = new ArrayDeque<>(); q.offer(root); int ans = 0; while (!q.isEmpty()) { ans = q.peek().val; for (int i = q.size(); i > 0; --i) { TreeNode node = q.poll(); if (node.left != null) { q.offer(node.left); } if (node.right != null) { q.offer(node.right); } } } return ans; } }
-
// OJ: https://leetcode.com/problems/find-bottom-left-tree-value/ // Time: O(N) // Space: O(N) class Solution { public: int findBottomLeftValue(TreeNode* root) { int ans = 0; queue<TreeNode*> q; q.push(root); while (q.size()) { int cnt = q.size(); ans = q.front()->val; while (cnt--) { root = q.front(); q.pop(); if (root->left) q.push(root->left); if (root->right) q.push(root->right); } } return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: q = deque([root]) ans = 0 while q: ans = q[0].val for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def findBottomLeftValue(self, root): """ :type root: TreeNode :rtype: int """ def dfs(root, h, w): if not root: return (float("inf"), float("inf"), None) left = dfs(root.left, h - 1, w - 1) right = dfs(root.right, h - 1, w + 1) return min((h, w, root.val), left, right) return dfs(root, 0, 0)[2]
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findBottomLeftValue(root *TreeNode) int { q := []*TreeNode{root} ans := 0 for len(q) > 0 { ans = q[0].Val for i := len(q); i > 0; i-- { node := q[0] q = q[1:] if node.Left != nil { q = append(q, node.Left) } if node.Right != nil { q = append(q, node.Right) } } } return ans }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function findBottomLeftValue(root: TreeNode | null): number { let ans = 0; const q = [root]; while (q.length) { ans = q[0].val; for (let i = q.length; i; --i) { const node = q.shift(); if (node.left) { q.push(node.left); } if (node.right) { q.push(node.right); } } } return ans; }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; use std::collections::VecDeque; impl Solution { pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { let mut queue = VecDeque::new(); queue.push_back(root); let mut res = 0; while !queue.is_empty() { res = queue.front().unwrap().as_ref().unwrap().borrow_mut().val; for _ in 0..queue.len() { let node = queue.pop_front().unwrap(); let mut node = node.as_ref().unwrap().borrow_mut(); if node.left.is_some() { queue.push_back(node.left.take()); } if node.right.is_some() { queue.push_back(node.right.take()); } } } res } }
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int bottomLeftValue = 0; while (!queue.isEmpty()) { int size = queue.size(); bottomLeftValue = queue.peek().val; for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); TreeNode left = node.left, right = node.right; if (left != null) queue.offer(left); if (right != null) queue.offer(right); } } return bottomLeftValue; } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> q = new ArrayDeque<>(); q.offer(root); int ans = 0; while (!q.isEmpty()) { ans = q.peek().val; for (int i = q.size(); i > 0; --i) { TreeNode node = q.poll(); if (node.left != null) { q.offer(node.left); } if (node.right != null) { q.offer(node.right); } } } return ans; } }
-
// OJ: https://leetcode.com/problems/find-bottom-left-tree-value/ // Time: O(N) // Space: O(N) class Solution { public: int findBottomLeftValue(TreeNode* root) { int ans = 0; queue<TreeNode*> q; q.push(root); while (q.size()) { int cnt = q.size(); ans = q.front()->val; while (cnt--) { root = q.front(); q.pop(); if (root->left) q.push(root->left); if (root->right) q.push(root->right); } } return ans; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: q = deque([root]) ans = 0 while q: ans = q[0].val for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def findBottomLeftValue(self, root): """ :type root: TreeNode :rtype: int """ def dfs(root, h, w): if not root: return (float("inf"), float("inf"), None) left = dfs(root.left, h - 1, w - 1) right = dfs(root.right, h - 1, w + 1) return min((h, w, root.val), left, right) return dfs(root, 0, 0)[2]
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findBottomLeftValue(root *TreeNode) int { q := []*TreeNode{root} ans := 0 for len(q) > 0 { ans = q[0].Val for i := len(q); i > 0; i-- { node := q[0] q = q[1:] if node.Left != nil { q = append(q, node.Left) } if node.Right != nil { q = append(q, node.Right) } } } return ans }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function findBottomLeftValue(root: TreeNode | null): number { let ans = 0; const q = [root]; while (q.length) { ans = q[0].val; for (let i = q.length; i; --i) { const node = q.shift(); if (node.left) { q.push(node.left); } if (node.right) { q.push(node.right); } } } return ans; }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; use std::collections::VecDeque; impl Solution { pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { let mut queue = VecDeque::new(); queue.push_back(root); let mut res = 0; while !queue.is_empty() { res = queue.front().unwrap().as_ref().unwrap().borrow_mut().val; for _ in 0..queue.len() { let node = queue.pop_front().unwrap(); let mut node = node.as_ref().unwrap().borrow_mut(); if node.left.is_some() { queue.push_back(node.left.take()); } if node.right.is_some() { queue.push_back(node.right.take()); } } } res } }