代码随想录day18
第9天
前言
主要知识点
● 513.找树左下角的值
● 112. 路径总和 113.路径总和ii
● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
- 思路一:
- 迭代法:使用层次遍历,始终保存在左边的元素,在遍历结束后,最左边的元素自然而然就存在了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if(root == null) return -1;
queue.offer(root);
int res = - 1;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0;i < size;i ){
TreeNode temp = queue.poll();
if(i == 0){
res = temp.val;
}
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
return res;
}
}
- 思路二:
递归法:
我们需要找最底层 最左边的叶子节点
最低层:我们需要前序遍历找到最大深度的叶子节点
最左边:前序遍历,没有处理的前提
class Solution {
int maxDepth = 0;
int res = -1;
public int findBottomLeftValue(TreeNode root) {
if(root == null) return res;
dfs(root,1);
return res;
}
public void dfs(TreeNode node,int depth){
if(node.left == null && node.right == null){
if(depth > maxDepth){
maxDepth = depth;
res = node.val;
}
}
if(node.left != null){
dfs(node.left,depth 1);
}
if(node.right != null){
dfs(node.right,depth 1);
}
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean flag ;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
flag = false;
flag = dfs(root,0,targetSum);
return flag;
}
public boolean dfs(TreeNode node,int res,int targetSum){
if(node.left == null && node.right == null){
if(res node.val == targetSum){
flag = true;
return true ;
}
return false;
}
boolean left = false,right = false;
if(node.left != null){
// System.out.println(node.val);
left = dfs(node.left,res node.val,targetSum);
}
if(node.right != null){
// System.out.println(node.val);
right = dfs(node.right,res node.val,targetSum);
}
return left || right;
}
}
从中序和后序遍历确定二叉树的排序
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
HashMap<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 findNode(inorder,0,inorder.length ,postorder,0,postorder.length );
}
public TreeNode findNode(int[] inorder,int inorderStartIndex,int inorderEndIndex,int[] postorder, int postorderStartIndex,int postorderEndIndex){
if( inorderStartIndex >= inorderEndIndex || postorderStartIndex >= postorderEndIndex){
return null;
}
TreeNode root = new TreeNode(postorder[postorderEndIndex -1]);
// if(postorderEndIndex - postorderStartIndex == 1) return root;
int rootIndex = map.get(postorder[postorderEndIndex -1]);
int LenOfleft = rootIndex - inorderStartIndex;
root.left = findNode(inorder,inorderStartIndex,rootIndex ,postorder,postorderStartIndex,postorderStartIndex LenOfleft);
root.right = findNode(inorder,rootIndex 1,inorderEndIndex,postorder,postorderStartIndex LenOfleft,postorderEndIndex -1);
return root;
// root.left = findNode(inorder, )
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfcige
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01