峰峰企业做网站推广,电脑培训机构,手机免费制作ppt,做搜狗手机网站点击软文章目录 说明题目 144. 二叉树的前序遍历题解 题目 94. 二叉树的中序遍历题解 题目 145. 二叉树的后序遍历题解 题目 105. 从前序与中序遍历序列构造二叉树题解 题目 106. 从中序与后序遍历序列构造二叉树题解 #x1f64a; 前言#xff1a;本文章为瑞_系列专栏之《刷题》的… 文章目录 说明题目 144. 二叉树的前序遍历题解 题目 94. 二叉树的中序遍历题解 题目 145. 二叉树的后序遍历题解 题目 105. 从前序与中序遍历序列构造二叉树题解 题目 106. 从中序与后序遍历序列构造二叉树题解 前言本文章为瑞_系列专栏之《刷题》的力扣LeetCode系列主要以力扣LeetCode网的题进行解析与分享。本文仅供大家交流、学习及研究使用禁止用于商业用途违者必究 说明 本文主要是配合《瑞_数据结构与算法_二叉树》对二叉树的知识进行提升和拓展
题目 144. 二叉树的前序遍历 原题链接Leetcode144. 二叉树的前序遍历 给你二叉树的根节点 root 返回它节点值的前序遍历。 示例 1 输入root [1,null,2,3] 输出[1,2,3] 示例 2 输入root [] 输出[] 示例 3 输入root [1] 输出[1] 示例 4 输入root [1,2] 输出[1,2] 示例 5 输入root [1,null,2] 输出[1,2] 提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗
题解
/*** 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 ListInteger preorderTraversal(TreeNode root) {/** 栈*/LinkedListTreeNode stack new LinkedList();/** 代表当前节点*/TreeNode current root;/** 最近一次弹栈的元素*/TreeNode pop null;ListInteger result new ArrayList();while (!stack.isEmpty() || current ! null) {if (current ! null) {stack.push(current);// 待处理左子树result.add(current.val);current current.left;} else {TreeNode peek stack.peek();// 没有右子树if (peek.right null) {// 获取最近一次弹栈的元素pop stack.pop();}// 右子树处理完成else if (peek.right pop) {// 获取最近一次弹栈的元素pop stack.pop();}// 待处理右子树else {current peek.right;}}}return result;}
}题目 94. 二叉树的中序遍历 原题链接Leetcode94. 二叉树的中序遍历 给定一个二叉树的根节点 root 返回 它的中序遍历 。 示例 1 输入root [1,null,2,3] 输出[1,3,2] 示例 2 输入root [] 输出[] 示例 3 输入root [1] 输出[1] 提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100 进阶: 递归算法很简单你可以通过迭代算法完成吗
题解
/*** 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 ListInteger inorderTraversal(TreeNode root) {/** 栈*/LinkedListTreeNode stack new LinkedList();/** 代表当前节点*/TreeNode current root;/** 最近一次弹栈的元素*/TreeNode pop null;ListInteger result new ArrayList();while (!stack.isEmpty() || current ! null) {if (current ! null) {stack.push(current);// 待处理左子树current current.left;} else {TreeNode peek stack.peek();// 没有右子树if (peek.right null) {result.add(peek.val);// 获取最近一次弹栈的元素pop stack.pop();}// 右子树处理完成else if (peek.right pop) {// 获取最近一次弹栈的元素pop stack.pop();}// 待处理右子树else {result.add(peek.val);current peek.right;}}}return result;}
}题目 145. 二叉树的后序遍历 原题链接Leetcode145. 二叉树的后序遍历 示例 1 输入root [1,null,2,3] 输出[3,2,1] 示例 2 输入root [] 输出[] 示例 3 输入root [1] 输出[1] 说明
树中节点的数目在范围 [0, 100] 内-100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗
题解
/*** 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 ListInteger postorderTraversal(TreeNode root) {/** 栈*/LinkedListTreeNode stack new LinkedList();/** 代表当前节点*/TreeNode current root;/** 最近一次弹栈的元素*/TreeNode pop null;ListInteger result new ArrayList();while (!stack.isEmpty() || current ! null) {if (current ! null) {stack.push(current);// 待处理左子树current current.left;} else {TreeNode peek stack.peek();// 没有右子树if (peek.right null) {// 获取最近一次弹栈的元素pop stack.pop();result.add(pop.val);}// 右子树处理完成else if (peek.right pop) {// 获取最近一次弹栈的元素pop stack.pop();result.add(pop.val);}// 待处理右子树else {current peek.right;}}}return result;}
}题目 105. 从前序与中序遍历序列构造二叉树 原题链接Leetcode105. 从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出: [3,9,20,null,null,15,7]示例 2: 输入: preorder [-1], inorder [-1]输出: [-1]提示:
1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列
题解 思路 1. 前序遍历preorder的第一个值肯定是根节点。通过preorder寻找根节点。2. 中序遍历inorder在根节点之前的值是根节点的左子树部分而之后的值是根节点的右子树部分。通过inorder区分左右子树部分。3. 通过循环inorder使用根节点确定中序遍历的左右子树部分、前序遍历的左右子树部分。4. 根据1.2.3.继续分为子问题递归解决。/*** 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 TreeNode buildTree(int[] preOrder, int[] inOrder) {if (preOrder.length 0) {return null;}// 创建根节点int rootValue preOrder[0];TreeNode root new TreeNode(rootValue);// 区分左右子树for (int i 0; i inOrder.length; i) {if (inOrder[i] rootValue) {// 0 ~ i-1 左子树// i1 ~ inOrder.length -1 右子树int[] inLeft Arrays.copyOfRange(inOrder, 0, i); int[] inRight Arrays.copyOfRange(inOrder, i 1, inOrder.length); int[] preLeft Arrays.copyOfRange(preOrder, 1, i 1);int[] preRight Arrays.copyOfRange(preOrder, i 1, preOrder.length); root.left buildTree(preLeft, inLeft); root.right buildTree(preRight, inRight); break;}}return root;}
}瑞可以使用HashMap优化以及新数组可以通过索引坐标参数传递优化。具体可见本系列HashMap章节后续更新 题目 106. 从中序与后序遍历序列构造二叉树 原题链接Leetcode106. 从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例1 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]输出[3,9,20,null,null,15,7]示例2 输入inorder [-1], postorder [-1]输出[-1]提示:
1 inorder.length 3000 postorder.length inorder.length-3000 inorder[i], postorder[i] 3000 inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历
题解 思路 1. 后序遍历postorder的最后一个元素就是根节点。通过postorder寻找根节点。2. 中序遍历inorder在根节点之前的值是根节点的左子树部分而之后的值是根节点的右子树部分。通过inorder区分左右子树部分。3. 通过循环inorder使用根节点确定中序遍历的左右子树部分、后序遍历的左右子树部分。4. 根据1.2.3.继续分为子问题递归解决。/*** 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 TreeNode buildTree(int[] inOrder, int[] postOrder) {if (inOrder.length 0) {return null;}// 根int rootValue postOrder[postOrder.length - 1];TreeNode root new TreeNode(rootValue);// 切分左右子树for (int i 0; i inOrder.length; i) {if (inOrder[i] rootValue) {int[] inLeft Arrays.copyOfRange(inOrder, 0, i);int[] inRight Arrays.copyOfRange(inOrder, i 1, inOrder.length);int[] postLeft Arrays.copyOfRange(postOrder, 0, i);int[] postRight Arrays.copyOfRange(postOrder, i, postOrder.length - 1);root.left buildTree(inLeft, postLeft);root.right buildTree(inRight, postRight);break;}}return root;}
}本文是博主的粗浅理解可能存在一些错误或不完善之处如有遗漏或错误欢迎各位补充谢谢 如果觉得这篇文章对您有所帮助的话请动动小手点波关注你的点赞收藏⭐️转发评论都是对博主最好的支持~
