题目描述

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

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

解题思路

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

代码实例

层次

<code>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--;

}

}

}