LeetCode刷题【513】找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1

示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7

注意: 您可以假设树（即给定的根节点）不为 NULL。

题解

BFS或者DFS

两个解法都写了，BFS看到网友有个写法，先插入右子节点，再插入左子节点，这样最终queue的最后一个节点，必定是最深一层，最左侧的节点，这样的好处是，不用分层循环

我的写法还是先插入左子节点，再插入右子节点，而每层循环的时候第一个peek到的值则是本层的最左侧节点

分层循环的时候，踩了个小坑，之前没太注意

//这是更正后的
int size = queue.size();
for (int i = 0; i < size; i++) {
    //poll逻辑
}

//更正前的
for (int i = 0; i < queue.size(); i++)

因为每次循环都会poll下，queue的size是会动态变化的，而每次循环的时候i值还在增加，会导致逻辑出错。

深搜DFS的时候也是，先遍历左节点，这样，只有深度更深的时候才更新查到的节点，深度相同的时候，肯定先取到的是左节点。

/**
 * 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) {
        dfs(root,0);

        bfs(root);
        return val;//theDeepNode.val
    }
    private int val;


    private TreeNode theDeepNode;

    private int depth = 0;

    private void dfs(TreeNode node, int currentDepth){
        if (null != node.left){
            dfs(node.left, currentDepth+1);
        }
        if (null != node.right){
            dfs(node.right, currentDepth+1);
        }
        if (node.left ==null && node.right == null){
            if (currentDepth > this.depth || this.theDeepNode == null){
                theDeepNode =  node;
                this.depth = currentDepth;
            }
        }
    }

    private Queue<TreeNode> queue = new LinkedList<>();

    private void bfs(TreeNode node){
        val = node.val;
        if (node.left!=null){
            queue.offer(node.left);
        }
        if (node.right!=null){
            queue.offer(node.right);
        }
        while (!queue.isEmpty()){
            val = queue.peek().val;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.poll();
                if (currentNode.left!=null){
                    queue.offer(currentNode.left);
                }
                if (currentNode.right!=null){
                    queue.offer(currentNode.right);
                }
            }
        }
    }

//
//    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;
//        }
//    }
}
//leetcode submit region end(Prohibit modification and deletion)