[leetCode513] 找树左下角的值(递归、迭代两种方法)

两种方法，迭代和递归。 看到这道题我的第一反应是树的层序遍历，找到最后一层的第一个节点就可以了，代码如下：

class Solution {
          
   
//利用队列实现层序遍历
    public int findBottomLeftValue(TreeNode root) {
          
   
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
          
   
            int size=queue.size();
            int t=0;
            for (int i=0;i<size;i++){
          
   
                TreeNode head = queue.poll();
                if (head.left!=null)    queue.add(head.left);
                if (head.right!=null)   queue.add(head.right);
                if (i==0) t=head.val;
            }
            if (queue.isEmpty())    return t;
        }
        return 0;
    }
}

也可以使用递归的方法，递归的终止条件是找到了叶子节点，找到之后判断是否更新了最大深度，如果更新了，就记录这个值。 那怎么判断它是这个深度的最左边的节点呢 ？ 其实是在递归的次序上做手脚，因为我们先递归左侧的子节点，所以第一次更新最大深度的时候，这个节点也一定是最左侧节点。下次如果遇到了同样深度的右侧节点，不会再触发更新。 代码如下：

public class Solution {
          
   
    int maxDepth=0;
    int leftVal=0;

    public int findBottomLeftValue(TreeNode root) {
          
   
        traversal(root,1);
        return this.leftVal;
    }

    public void traversal(TreeNode root,int leftLen){
          
   
        if (root.left==null&&root.right==null){
          
   
            if (leftLen>maxDepth){
          
   
                maxDepth=leftLen;
                leftVal= root.val;
            }
            return;
        }
        if (root.left!=null) traversal(root.left,1+leftLen);
        if (root.right!=null) traversal(root.right,1+leftLen);
    }
}