以上思路来自于:代码随想录 (programmercarl.com)
LeetCode T513 找树左下角的值
题目思路:
本题思路:这题我们使用递归法和迭代法解决问题
注意:左下角的值不一定就是一直向左遍历的叶子结点的值,首先可以确定是最后一行的第一个叶子结点的值,也就是最大深度的叶子结点的值
定义最大深度Deep变量,返回值result
1.递归法
前序遍历为例
1.1 确定递归的返回值和参数类型
我们这里不需要返回值,传入参数是节点和深度
void travelsal(TreeNode node,int deep)
1.2 确定终止条件
这里我们遇到一次叶子结点就更新一次最大深度,并记录下该节点的val
if(node.left == null && node.right == null) { if(deep>Deep) { Deep = deep; result = node.val; } }
1.3 实现一次递归
if(node.left != null) { travelsal(node.left,deep+1); } if(node.right != null) { travelsal(node.right,deep+1); }
2.迭代法
思路:使用层序遍历,找到最后一行,记录下最左边节点的数值
1.使用队列结构,队列不为空就继续,先加入根节点,接着我们用一个临时节点记录一下正在遍历的节点,方便取值,使用for循环,遍历每一层,记录下每一层第一个值,如果不是叶子节点就继续入队,详细思路可以看 层序遍历章节
代码解析:
public int findBottomLeftValue(TreeNode root) { //迭代法 int result = 0; Queue<TreeNode> que = new LinkedList<>(); que.offer(root); while(!que.isEmpty()) { int size = que.size(); for(int i = 0;i<size;i++) { TreeNode tmp = que.poll(); if(i == 0) { result = tmp.val; } if(tmp.left != null) { que.offer(tmp.left); } if(tmp.right != null) { que.offer(tmp.right); } } } return result; } }
题目代码:
class Solution { int Deep = -1; int result = 0; public int findBottomLeftValue(TreeNode root) { result = root.val; travelsal(root,0); return result; } void travelsal(TreeNode node,int deep) { if(node == null) { return; } if(node.left == null && node.right == null) { if(deep>Deep) { Deep = deep; result = node.val; } } if(node.left != null) { travelsal(node.left,deep+1); } if(node.right != null) { travelsal(node.right,deep+1); } } }
LeetCode T112 路径总和
题目思路:
思路其实很简单,我们只需要遍历二叉树在叶子节点的时候判断即可,但是还是有很多细节需要注意,我们分一下几步操作,判断节点是否为空,减去该节点的值,判断叶子结点的值,下面就是递归的过程
1.判断头结点
if(root == null) { return false; }
2.叶子节点
//叶子结点 if(root.left == null && root.right == null) { return targetSum == 0; }
3.递归过程
//递归逻辑 if(root.left != null) { boolean left = hasPathSum(root.left,targetSum); if(left) { return true; } } if(root.right != null) { boolean right = hasPathSum(root.right,targetSum); if(right) { return true; } }
注:我们这里用目标值一直往下减,如果到叶子节点发现值减到0就说明成功了,注意回溯的过程这里省略了.
题目代码:
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) { boolean left = hasPathSum(root.left,targetSum); if(left) { return true; } } if(root.right != null) { boolean right = hasPathSum(root.right,targetSum); if(right) { return true; } } return false; } }
T106 从中序和后序遍历构造二叉树
题目链接:106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
题目思路:
这题思路较为简单,代码较长,我们举一个例子
我们首先根据后序的左右中来切割中序数组,就能知道9是左子树,15 20 7是右子树
然后根据右子树判断中节点是20,20的左节点是15右节点是7,我们就能唯一确定一个二叉树
这里我们分为以下几步处理
1.创建一个map来便于查找
2.将inorder的数据保存到map中 (key是数值,value是下标)
3.接着我们使用递归来实现
4.确定参数和返回值
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd)
5.终止条件(注意这里切分区间要统一,使用闭区间还是左开右闭区间)
if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树 return null; }
6.单次递归
int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数 root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft); root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
题目代码:
class Solution { Map<Integer,Integer> map; public TreeNode buildTree(int[] inorder, int[] postorder) { map = new HashMap<>(); for(int i = 0;i<inorder.length;i++) { map.put(inorder[i],i); } return FindOrder(inorder,0,inorder.length,postorder,0,postorder.length); } public TreeNode FindOrder(int[] inOrder,int inBegin,int inEnd,int[] postOrder,int postBegin,int postEnd) { //结束条件,这里我使用左闭右开写 if(inBegin>=inEnd || postBegin>=postEnd) { return null; } //找到后序在中序的位置 int index = map.get(postOrder[postEnd - 1]); //构造节点 TreeNode root = new TreeNode(inOrder[index]); //保存中序左子树的个数,用来确定后序的区间 int lenOfLeft = index - inBegin; root.left = FindOrder(inOrder,inBegin,index,postOrder,postBegin,postBegin+lenOfLeft); root.right = FindOrder(inOrder,index+1,inEnd,postOrder,postBegin+lenOfLeft,postEnd-1); return root; } }
