LeetCode - Medium - 513. Find Bottom Left Tree Value

朴灿烈づ我的快乐病毒、 2022-10-16 09:49 161阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search

## Description ##

[https://leetcode.com/problems/find-bottom-left-tree-value/][https_leetcode.com_problems_find-bottom-left-tree-value]

Given the root of a binary tree, return the leftmost value in the last row of the tree.

**Example 1:**

![884cac6be3ebbce496bf9d4628361377.png][]

Input: root = [2,1,3]
    Output: 1

**Example 2:**

![a71aa4cbc4614a6d485a0c9f24431e9f.png][]

Input: root = [1,2,3,4,null,5,6,null,null,7]
    Output: 7

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\].
 *   − 2 31 ⩽ N o d e . v a l ⩽ 2 31 − 1 -2^\{31\} \\leqslant Node.val \\leqslant 2^\{31\} - 1 −231⩽Node.val⩽231−1

## Analysis ##

方法一：BFS

方法二：BFS，比方法一的更简洁。与方法一的区别，本方法先添加右子树到队列，然后才是左子树

方法三：DFS

## Submission ##

import java.util.LinkedList;
    import java.util.Queue;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindBottomLeftTreeValue { 
    	
    	//方法一：BFS
        public int findBottomLeftValue(TreeNode root) { 
            
        	LinkedList<TreeNode> queue = new LinkedList<>();
        	queue.offer(root);
        	
        	TreeNode leftmost = null;
        	
        	while(!queue.isEmpty()) { 
        		
        		int originalSize = queue.size();
        		for(int size = originalSize; size > 0; size--) { 
        			TreeNode node = queue.poll();
        			
        			if(size == originalSize)
        				leftmost = node;
        			
        			if(node.left != null)
        				queue.offer(node.left);
        			if(node.right != null)
        				queue.offer(node.right);
        		}
        		
        	}
        	
        	return leftmost.val;
        }
        
        //方法二：BFS，比方法一更简洁
        public int findBottomLeftValue2(TreeNode root) { 
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                root = queue.poll();
                
                //从 右子树 到 左子数
                if (root.right != null)
                    queue.add(root.right);
                if (root.left != null)
                    queue.add(root.left);
            }
            return root.val;
        }
        
        //方法三：DFS
        public int findBottomLeftValue3(TreeNode root) { 
        	int[] leftmost = { 0}, depth = { 0};
        	findBottomLeftValue3(root, 1, leftmost, depth);
        	return leftmost[0];
        }
        
        
        private void findBottomLeftValue3(TreeNode node, int height, int[] leftmost, int[] depth) { 
        	if(node == null) return;
        	
        	if(height > depth[0]) { 
        		leftmost[0] = node.val;
        		depth[0] = height;
        	}
        	
        	findBottomLeftValue3(node.left, height + 1, leftmost, depth);
        	findBottomLeftValue3(node.right, height + 1, leftmost, depth);
        }
        
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindBottomLeftTreeValueTest { 
    
    	@Test
    	public void test() { 
    		FindBottomLeftTreeValue obj = new FindBottomLeftTreeValue();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(2,1,3);
    		TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3, 4, null, //
    													5, 6, null, null, 7);
    		
    		assertEquals(1, obj.findBottomLeftValue(root1));
    		assertEquals(7, obj.findBottomLeftValue(root2));
    		
    		assertEquals(1, obj.findBottomLeftValue2(root1));
    		assertEquals(7, obj.findBottomLeftValue2(root2));
    		
    		assertEquals(1, obj.findBottomLeftValue3(root1));
    		assertEquals(7, obj.findBottomLeftValue3(root2));
    	}
    }

[https_leetcode.com_problems_find-bottom-left-tree-value]: https://leetcode.com/problems/find-bottom-left-tree-value/
[884cac6be3ebbce496bf9d4628361377.png]: /images/20221014/7b8b8495a96e4ba8983e4d34105440b0.png
[a71aa4cbc4614a6d485a0c9f24431e9f.png]: /images/20221014/75a8b00e0b124096a1da670bff78ff59.png