package question;

import java.util.LinkedList;
import java.util.Queue;

/*
 @author: Roderland
 @create: 2020年08月16日---15:35
*/
public class Question513 {
 public int findBottomLeftValue(TreeNode root) {
 return fun(root, depth(root));
 }
 public int depth(TreeNode root) {
 if (root==null) return 0;
 return 1+Math.max(depth(root.left), depth(root.right));
 }
 public int fun(TreeNode root, int depth) {
 if (root==null) return -1;
 if (depth==1) return root.val;
 int l = fun(root.left, depth-1);
 int r = fun(root.right, depth-1);
 if (l!=-1) return l;
 return r;
 }

 public static void main(String[] args) {
 //[1,2,3,4,null,5,6,null,null,7]
 TreeNode t1 = new TreeNode(1);
 TreeNode t2 = new TreeNode(2);
 TreeNode t3 = new TreeNode(3);
 TreeNode t4 = new TreeNode(4);
 TreeNode t5 = new TreeNode(5);
 TreeNode t6 = new TreeNode(6);
 TreeNode t7 = new TreeNode(7);
 t1.left=t2;
 t1.right=t3;
 t2.left=t4;
 t3.left=t5;
 t3.right=t6;
 t5.left=t7;
 System.out.println(new Question513().findBottomLeftValue2(t1));
 }

 //solution2
 public int findBottomLeftValue2(TreeNode root) {
 Queue<TreeNode> queue = new LinkedList<>();
 queue.offer(root);
 TreeNode cur = root;
 while (!queue.isEmpty()) {
 cur = queue.peek();
 int length = queue.size();
 for (int i = 0; i < length; i++) {
 TreeNode pop = queue.poll();
 if (pop.left!=null) queue.offer(pop.left);
 if (pop.right!=null) queue.offer(pop.right);
 }
 }
 return cur.val;
 }
}