513、找树左下角的值
基本思想:
树的最后一行找到最左边的值
树的最后一行:深度最大的叶子节点---前序遍历
最左边:优先左边搜索---前序遍历
具体实现:
1、确定递归参数和返回值
参数:根节点和int型变量记录深度
返回值:不需要
如果要遍历整棵树,递归函数不能有返回值
如果要遍历某一条固定路线,递归函数就一定要返回值
本题要遍历整个树找到最深的叶子节点,需要遍历整棵树,所以没有返回值
2、终止条件
遇到叶子节点,统计一下最大的深度了,所以需要遇到叶子节点来更新最大深度maxLen。
if (root.left == null && root.right == null){ if (leftLen > maxLen) { maxLen = leftLen; maxLeftValue = root.val; } return; }
3、单层递归逻辑
回溯
代码:
class Solution { private int maxLen = -1; private int maxLeftValue = 0; public int findBottomLeftValue(TreeNode root) { findLeftValue(root,0); return maxLeftValue; } private void findLeftValue (TreeNode root, int leftLen){ if (root == null) return; if (root.left == null && root.right == null){ if (leftLen > maxLen) { maxLen = leftLen; maxLeftValue = root.val; } return; } if (root.left != null){ leftLen++; findLeftValue(root.left,leftLen); leftLen--; } if(root.right != null){ leftLen++; findLeftValue(root.right,leftLen); leftLen--; } return; } }
迭代法
class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int res = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode poll = queue.poll(); if (i == 0) { res = poll.val; } if (poll.left != null) { queue.offer(poll.left); } if (poll.right != null) { queue.offer(poll.right); } } } return res; } }