513.找树左下角的值
第一想法
既然提示说迭代比递归简单一点，那就是找到到最后一层的第一个节点然后返回。那么怎么确定是最后一层呢？
每层遍历时先标记第一个节点tempNode,设置此层是否为最后一层标记flag = true。如果加入非空节点那么说明还有下层，此层就不是最后一层，flag=false。此层遍历解说后flag=true，那么就返回tempNode。
代码随想录
一直向左遍历不是二叉树的左下角，深度最大的叶子节点一定是最后一行。那么如何求得第一个节点呢？前序：中左右，中序：左中右，后序：左右中。本题没有中节点的处理逻辑，那么三种方式其实都相当于优先遍历左节点。一旦得到了深度最大得叶子节点，那么它一定是最靠近左侧的。
最靠左侧的值未必就是左孩子，只要优先遍历左侧就可以。
如果是层序遍历则不用很麻烦，每层遍历记录第一个节点。所有层遍历完后直接返回这个记录值即可。它一定是最后一层得第一个节点。
代码
class Solution {
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int result = 0;
while (!deque.isEmpty()){
int size = deque.size();
for (int i = 0; i < size; i++) {
TreeNode tempNode = deque.poll();
if(i==0)result = tempNode.val;
if(tempNode.left!=null)deque.offer(tempNode.left);
if(tempNode.right!=null)deque.offer(tempNode.right);
}
}
return result;
}
}
class Solution1 {
int maxDepth = Integer.MIN_VALUE;
int result = 0;
public int findBottomLeftValue(TreeNode root) {
traversal(root,1);
return result;
}
public void traversal(TreeNode root,int depth){
//终止条件,首先是叶子节点
if(root.left==null&&root.right==null){
if(depth>maxDepth){
maxDepth = depth;
result = root.val;
}
return;
}
//优先遍历左节点
if(root.left!=null){
depth++;
traversal(root.left,depth);
depth--;//回溯,深度-1
}
//再遍历右节点
if(root.right!=null){
depth++;
traversal(root.right,depth);
depth--;
}
//中间节点是不做处理的。
}
}路径总和
题目链接：112. 路径总和 - 力扣（LeetCode） 113. 路径总和 II - 力扣（LeetCode）
文档/视频链接：代码随想录 (programmercarl.com)
代码随想录
返回值是Boolean，在这颗二叉树里只需要找到一条路径符合返回直接返回就可以，没有必要遍历所有的节点。所以一旦到叶子节点发现符合要求后，就一路将true返回直至根节点。
参数：计数器 count，TreeNode node
正向思考是：传入0，每遇到一个节点，就加val，看看是不是与target相等。
反向思考：更简单一些，这里直接传入目标值。遇到一个节点就减val。如果到叶子节点，该数值减为0，那么沿此路的所有节点相加恰好等于target。
终止条件：叶子节点并且count为0，return true。
叶子节点但count不为0，return false。
单层递归逻辑：
以上没有对root做判空。
若左不为空：count减左节点的值，递归遍历左孩子。如果左孩子遍历返回来的值是true，则左方向有符合题目要求的路径，那么就应该将这个true结果继续向上返回。回溯将左方向的值加回来。
若右不为空：
如果都没有返回true，那么最终返回false
代码
//LeetCode112
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)return false;
targetSum -= root.val;
if(root.left==null&&root.right==null)return targetSum==0;
if(root.left!=null){
if(hasPathSum(root.left,targetSum)) return true;
}
if(root.right!=null){
if (hasPathSum(root.right,targetSum))return true;
}
return false;
}
}LeetCode113，自己写的有错误，还没找出来原因。
class Solution {
List<List<Integer>> result;
LinkedList<Integer> path;
public List<List<Integer>> pathSum (TreeNode root,int targetSum) {
result = new LinkedList<>();
path = new LinkedList<>();
travesal(root, targetSum);
return result;
}
private void travesal(TreeNode root, int count) {
if (root == null) return;
path.offer(root.val);
count -= root.val;
if (root.left == null && root.right == null && count == 0) {
result.add(new LinkedList<>(path));
}
travesal(root.left, count);
travesal(root.right, count);
path.removeLast(); // 回溯
}
}106.从中序与后序遍历序列构造二叉树
题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
文档/视频链接：代码随想录 (programmercarl.com)
代码随想录想法
框架：
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0||postorder.length==0)
return null;
return buildHelper(inorder,0,inorder.length,postorder,0,postorder.length);
}
public TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
if(postorderStart==postorderEnd)return null;
int rootValue = postorder[postorderEnd - 1];
TreeNode root = new TreeNode(rootValue);
int middleIndex;
for(middleIndex = inorderStart;middleIndex<inorderEnd;middleIndex++){
if(inorder[middleIndex]==rootValue)
break;
}
//[leftInorderStart,leftInorderEnd)
int leftInorderStart = inorderStart;
int leftInorderEnd = middleIndex;
int rightInorderStart = middleIndex+1;
int rightInorderEnd = inorderEnd;
int leftPostorderStart = postorderStart;
int leftPostorderEnd = postorderStart+(leftInorderEnd-leftInorderStart);
int rightPostorderStart = leftPostorderEnd;
int rightPostorderEnd = postorderEnd-1;
root.left = buildHelper(inorder,leftInorderStart,leftInorderEnd,postorder,leftPostorderStart,leftPostorderEnd);
root.right = buildHelper(inorder,rightInorderStart,rightInorderEnd,postorder,rightPostorderStart,rightPostorderEnd);
return root;
}
}
