找树左下角的值-513

题目描述

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

解题思路

这道题用层次遍历的方式来说是比较简单的，用递归的话如果我们看别人的精简代码很难看出其中隐藏的细节，这里递归遍历其实我们用到了回溯的思想，我们直接采用前序遍历的方式(其实三种遍历方式都是一样的)，定义一个max_depth作为参考值记录当前遍历子树的最大深度，如果我们遍历到了叶子节点而且其深度大于这个max_depth我们就可以进行赋值操作，反之则不用，因为深度没有它大的话肯定不是最后一层的叶子节点，没有我们上一次遍历子树的层次高，就无需进行赋值操作

代码实例

层次

import java.util.*; 
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque=new LinkedList<>();
        deque.add(root);
        List<Integer> result=new ArrayList<>();
        // result.add(root.val);
        while(!deque.isEmpty()){
            int size=deque.size();
            for(int i=0;i<size;i++){
                TreeNode temp=deque.pollFirst();
                result.add(temp.val);
                if(temp.right!=null){
                    deque.addLast(temp.right);
                }
                if(temp.left!=null){
                    deque.addLast(temp.left);
                }
            }

        }

        return result.get(result.size()-1);


    }
}

递归

import java.util.*;

class Solution {
    int max_depth=Integer.MIN_VALUE;
    int result=0;
    public int findBottomLeftValue(TreeNode root) {
    
        bianli(root,1);
        return result;
    }

    public void bianli(TreeNode root,int depth) {
        if(root.left==null && root.right==null){
            if(depth>max_depth){
                max_depth=depth;
                result=root.val;
            }
        }
        
        if(root.left!=null){
            bianli(root.left,++depth);
        // 回溯的思想，我们要减去depth然后回溯到根节点然后再从1开始去遍历我们的右子树
            depth--;
        }

        if(root.right!=null){
            bianli(root.right,++depth);
            depth--;
        }

    }
}