LeetCode - Medium - 513. Find Bottom Left Tree Value-蒲公英云

LeetCode - Medium - 513. Find Bottom Left Tree Value

Topic

Tree
Depth-first Search
Breadth-first Search

Description

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:

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

Example 2:

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