做地方网站收益怎么样,局域网如何做网站,做一下网站需要什么时候开始,北京网页制作培训班一、树形结构
1、什么是树形结构
根节点没有前驱#xff0c;其它节点只有一个前驱#xff08;双亲/父结点#xff09;。所有节点可以有 0 ~ 多个后继#xff0c;即分支#xff08;孩子结点#xff09;。每个结点作为子树的根节点#xff0c;这些子树互不相交。 2、关于…一、树形结构
1、什么是树形结构
根节点没有前驱其它节点只有一个前驱双亲/父结点。所有节点可以有 0 ~ 多个后继即分支孩子结点。每个结点作为子树的根节点这些子树互不相交。 2、关于树概念词
节点的度节点的分支数。
树的度树中最大的结点的度。
节点的层次根为第一层。
树的高度最大层次。
兄弟结点同父的结点
堂兄弟结点同爷爷的结点。
节点的祖先从根到该结点路径上的所有结点。
子孙某节点为根其子树中任意结点。
森林互不相交的树集合。
3、树的表示形式 很多种简单了解最常用这种表示法方便将树转为二叉树的孩子兄弟表示法
class Node {int data; // 存数据Node firstChild; // 存第一个孩子Node firstBrother; // 存第一个兄弟
}
二、二叉树
1、什么是二叉树
树的度为2。子树有左右之分不能颠倒。
2、特殊的二叉树
满二叉树若k表示结点层数则每层结点数都等于 2^(k-1) 的树就是满二叉树。完全二叉树每个结点编号与满二叉树中每个节点编号一一对应的树。
3、二叉树性质
3.1、性质
第 k 层最多有 2^(k-1) 个结点。高度为 k 的二叉树最多有 (2^k) - 1 个结点。任意二叉树叶子节点个数 n0 和有两个度的结点个数 n2 有关系n0 n21。
推导n n0n1n2 个结点除了根节点都有前驱故一共 n-1 个度。n-1 0*n01*n12*n2。
联合两个式子得到n0 n2 1。
n 个节点的完全二叉树深度为 log(n1) 上取整。
推导n (2^k)-1k log(n1)。完全二叉树结点数肯定小于等于满二叉树结点数所以 n 可能不够结果就上取整。
从根节点开始编号0从左往右给每个结点编号
① 双亲编号 i0根节点无双亲i0双亲编号(i-1)/2。
② 左孩子编号若 2*i1 n左孩子编号 2*i1否则没左孩子。
③ 右孩子编号若 2*i2 n右孩子编号 2*i2否则没右孩子。
3.2、练习题 4、二叉树的遍历
4.1、遍历方式 前序根左右ABDCEF。
中序左根右DBAECF。
后序左右根DBEFCA。
层序从上到下从左往右ABCDEF。
4.2、遍历序列转二叉树 如果想根据遍历序列获得二叉树则必须是两种遍历序列并且其中一种必须是中序遍历。因为前、后、层序遍历序列能得知每个子二叉树的根中序遍历能得知某根的左右子树。 4.3、代码递归 二叉树的存储结构有顺序存储和链式存储本文只讨论了链式存储。顺序存储请看我写的优先级队列堆部分。 二叉树的表示形式
public class BinaryTree {public static class TreeNode {char value;TreeNode left;TreeNode right;public TreeNode(char value) {this.value value;}}private TreeNode root;............
} 构造一棵二叉树主要为了测试这种构造方式不可取 public void createTree() {TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);A.left B;A.right C;B.left D;C.left E;C.right F;root A;} 前序遍历 public static void preOrder(TreeNode root) {if (root null) {return;}System.out.print(root.value );preOrder(root.left);preOrder(root.right);} 中序遍历 public static void inOrder(TreeNode root) {if (root null) {return;}inOrder(root.left);System.out.print(root.value );inOrder(root.right);} 后序遍历 public static void postOrder(TreeNode root) {if (root null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.value );}
4.4、代码非递归 前序遍历144. 二叉树的前序遍历 - 力扣LeetCode 分析深度优先遍历左子树遍历完后转到右子树需要获得父亲结点属于后进先出用栈实现。 对于非空树当前处理子树的根 cur 的初始值为 root。 step1树不为空树根 cur 入栈并打印。若左子树不为空更新子树 cur 为左子树重复step1。直到遇到左子树为空即 cur 为空停止上述循环。转到step2开始判断右子树。 step2弹出栈顶元素即左子树的父结点用于转到右子树若右子树为空重复step2。直到栈为空且右子树仍为空时树遍历完成或者遇到右子树不为空更新子树 cur 为右子树重复 step1开始遍历右子树。
class Solution {public ListInteger preorderTraversal(TreeNode root) {StackTreeNode stack new Stack(); // 栈用于左子树遍历完后获取父节点转到遍历右子树ListInteger list new ArrayList(); // 打印序列// 空树不打印if(root null) {return list;}TreeNode cur root; // 当前处理子树的根。对于非空树初始值为 root。// 栈不为空说明还有右子树需要判断// cur不为空说明还有非空右子树需要遍历while(!stack.isEmpty() || cur ! null) { // step1// 一直是 push 操作不需要判断栈空// 处理情况1直到左子树为空退出循环再转到 step2// 处理情况2右子树不为空需要遍历右子树转到 step1while(cur ! null) {stack.push(cur); // 当前处理子树的根节点入栈list.add(cur.val); // 打印当前处理子树的根结点cur cur.left; // 转到左子树}// step2cur stack.pop(); // 弹出栈顶元素cur cur.right; // 转到右子树}return list;}
} 也可以用 ArrayDeque 替代 Stack区别是 Stack 的方法有 synchronized 关键字修饰在多线程环境中用锁实现同步。比如有一个 Stack 对象 p1当一个线程使用了 p1调用的同步方法那么 p1 对象的同步方法就会被锁住使得其它的线程不能调用 p1 的同步方法直到那个线程使用完后解锁其它线程才能够使用。因此在多线程环境中Stack 相较于 ArrayDeque 是线程安全的。 中序遍历94. 二叉树的中序遍历 - 力扣LeetCode 分析左根右根保存在栈中。先遍历左子树左子树遍历完后弹出根时打印根最后遍历右子树。依然是用栈保存父节点用于转向右子树。 方法与前序遍历类似只不过打印根的位置不同。
class Solution {public ListInteger inorderTraversal(TreeNode root) {StackTreeNode stack new Stack();ListInteger list new ArrayList(); if(root null) {return list;}TreeNode cur root; while(!stack.isEmpty() || cur ! null) { while(cur ! null) {stack.push(cur); cur cur.left; }cur stack.pop(); list.add(cur.val); // 弹出父节点根结点时才打印根cur cur.right; }return list;}
} 后续遍历145. 二叉树的后序遍历 - 力扣LeetCode 分析左右根左子树遍历完后父节点不能弹出栈右子树遍历完后父节点再弹出栈打印。 我们现在需要思考右子树遍历完的标志是什么。比如上图这棵树在遍历到 F 时栈中元素应该为A, C, F。当前父节点 F 的左子树为 null 不遍历右子树也为 null 不遍历弹出根 F 并打印此时栈为AC。当前父节点 C 的右子树是FF已遍历完需要弹出根C并打印...... 可以观察到当前父节点栈顶元素的右子树为空或者父节点的右孩子是上一次弹出的栈顶元素时 表示右子树遍历结束。
class Solution {public ListInteger postorderTraversal(TreeNode root) {StackTreeNode stack new Stack();ListInteger list new ArrayList(); if(root null) {return list;}TreeNode cur root; TreeNode pre null; // 存储上一次遍历完成的子树的根while(!stack.isEmpty() || cur ! null) { while(cur ! null) {stack.push(cur); cur cur.left; }TreeNode top stack.peek(); // 查看父节点元素继续判断是否要遍历右子树// 父节点的右孩子为空或者父节点的右孩子是上一次遍历完的子树上一次弹出的根则表示其右子树遍历完成// cur 不能改变仍为 null表示右子树已经遍历完了不需要再在step1中遍历。所以用 top 暂存父节点if(top.right null || top.right pre) {stack.pop(); // 弹出父节点list.add(top.val); // 打印父节点pre top; // 保存遍历完的子树的根} else { // 右子树没遍历完继续遍历父节点的右子树cur top.right; }}return list;}
} 层序遍历使用队列根节点开始从上往下从左到右先进先出。每弹出一个结点打印该节点让后将其孩子全部依次入队。直到队列为空结束。 public void levelOrder() {QueueTreeNode queue new LinkedList(); // 队列if (root null) { // 空树return;}queue.offer(root); // 根节点入队while (!queue.isEmpty()) {TreeNode node queue.poll(); // 出队System.out.print(node.value ); // 打印if (node.left! null) { // 左孩子不为空入队queue.offer(node.left);}if (node.right! null) { // 右孩子不为空入队queue.offer(node.right);}}}
5、二叉树的基本操作
5.1、求树中节点个数 遍历思想把遍历中的打印结点换为计数结点。 private int count; public int size() {count 0;size(root);return count;}public void size(TreeNode root) {if (root null) {return;}count;size(root.left);size(root.right);} 子问题思想树的结点树左数结点数右数结点数1。 public static int size2(TreeNode root) {if (root null) { // 空树0个结点return 0;}return size2(root.left) size2(root.right) 1;}
5.2、求叶子节点个数 遍历思想把打印结点换为是叶子结点就计数。 private int leafCount;public int leafCount() {leafCount 0;leafCount(root);return leafCount;}public void leafCount(TreeNode root) {if (root null) {return;}if (root.left null root.right null) {leafCount;} leafCount(root.left);leafCount(root.right);} 子问题思想树的叶子结点个数左子树叶子节点个数右子树叶子节点个数。 public static int leafCount2(TreeNode root) {if (root null) { // 空树0个叶子节点return 0;}if (root.left null root.right null) { // 只有一个根结点1个叶子节点return 1;}return leafCount2(root.left) leafCount2(root.right);}
5.3、求第K层结点个数 遍历思想把打印结点换成是第 K 层结点就计数。遍历整棵树。 private int levelCount;public int levelCount(int k) {levelCount 0;levelCount(root, k);return levelCount;}public void levelCount(TreeNode root, int k) {if (root null) {return;}if (k 1) {levelCount;}levelCount(root.left, k - 1);levelCount(root.right, k - 1);} 子问题思想树的第K层结点个数左子树的第K-1层节点个数右子树的第K-1层节点个数。如果K合法到第K层为止效率比遍历思想更高。 public static int levelCount2(TreeNode root, int k) {if (root null) { // 空树没有节点return 0;}if (k 1) { // 树的第一层结点为根1个节点return 1;}return levelCount2(root.left, k - 1) levelCount2(root.right, k - 1);}
5.3、求二叉树的高度 子问题思想树的高度max(左子树高度右子树高度)1。 时间复杂度调用递归函数的次数O(n)。 空间复杂度因为调用到叶子节点后就会释放空间再遍历另一个分叉因此空间复杂度是树的高度O(logN)。 public static int height(TreeNode root) {if (root null) { // 空树深度为0return 0;}return Math.max(height(root.left), height(root.right)) 1;}
5.4、检测 value 是否在树中 子问题思想是根返回根节点地址搜索左子树返回值不为空返回地址搜索右子树返回值不为空返回地址否者返回 nll。 最坏时间复杂度O(N) public static TreeNode findValue(TreeNode root, char value) {if (root null) { // 树为空没有结点return null; }if (root.value value) { // 是根节点return root;}TreeNode left findValue(root.left, value); // 搜索左子树if (left! null) { // 找到了return left;}return findValue(root.right, value); // 搜索右子树}
5.5、判断树是否为完全二叉树 思路空树必为完全二叉树。层序遍历树空结点要入队。遇到第一个空结点如果是完全二叉树则在队列中这个空结点的右边必全是空结点如果不是完全二叉树在队列中其右必存在不为空结点。 故遇到空结点后马上在队列中判断其后是否都为空是则为完全二叉树否则不为。 public static boolean isComplete(TreeNode root) {if(root null) { // 空树return true;}QueueTreeNode queue new LinkedList(); // 队列queue.offer(root); // 根节点入队while (!queue.isEmpty()) { // 层序遍历树寻找树中第一个空结点TreeNode node queue.poll(); // 弹出一个结点if (node ! null) {queue.offer(node.left); // 左孩子入队queue.offer(node.right); // 右孩子入队} else { // 遇到空结点退出循环break;}}// 判断空结点后是否都为空姐点while (!queue.isEmpty()) {if (queue.poll() ! null) { // 还有非空结点不是完全二叉树return false;}}return true;}
6、二叉树相关OJ题
6.1、分层包装
102. 二叉树的层序遍历 - 力扣LeetCode 分析在正常前序遍历的基础上根节点入队得到初始队列。 依次出队包装为一层添加到树中。其孩子依次入队作为下一层。 重复上述操作直到下一层为空。 class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();if(root null) { // 空树return list;}// 初始根节点入队QueueTreeNode queue new LinkedList(); // 下一层队列queue.offer(root); while(!queue.isEmpty()) { // 直到下一层为空ListInteger curLevel new ArrayList(); // 当前层 int size queue.size(); // 处理下一层下一层作为当前层的大小while(size-- ! 0) { // 遍历队列包装为层将每个结点的孩子放入下一层TreeNode node queue.poll(); // 弹出一个结点curLevel.add(node.val); // 包装到当前层中if(node.left ! null) { // 左孩子放入下一层queue.offer(node.left);}if(node.right ! null) { // 右孩子放入下一层queue.offer(node.right);}}list.add(curLevel);}return list;}
}
6.2、两颗相同的树
100. 相同的树 - 力扣LeetCode
分析子问题思想。两根为空必相同。一根为空一根不为空必不相同。两根不为空两值不同必不相同两值相同两棵树的左子树相同且右子树相同则相同否则不同。
时间复杂度O(min(n, m))最坏情况结点数最少的那棵树遍历完就知道是否相同了。
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p null q null) { // 两空树相同return true;}if((p null q ! null) || (p ! null q null)) { // 一根空一根不空不相同return false;}// 两根不为空if(p.val ! q.val) { // 值不相同不相同return false;}// 两根相同左、右子树相同才相同否则不同return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}
}
6.3、另一棵树的子树
572. 另一棵树的子树 - 力扣LeetCode 分析子问题思想。树为空没有子树子树与树相同是子树子树与树不相同子树是不是树的左子树的子树是则是子树子树是不是树的右子树的子树是则是子树否则不是子树。
时间复杂度O(m*n)每遇树中一个结点就遍历子树是否与之相等。m 个结点比较 m 次每次比较 n 个子树结点。
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p null q null) { // 两空树相同return true;}if((p null q ! null) || (p ! null q null)) { // 一根空一根不空不相同return false;}// 两根不为空if(p.val ! q.val) { // 值不相同不相同return false;}// 两根相同左、右子树相同才相同否则不同return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root null) { // 树为空没有子树return false;}if (isSameTree(root, subRoot)) { // 树和子树相同是树的子树return true;}if(isSubtree(root.left, subRoot)) { // 是左子树的子树是树的子树return true;}return isSubtree(root.right, subRoot); // 是右子树的子树是树的子树否则不是树的子树}
}
6.4、翻转二叉树
226. 翻转二叉树 - 力扣LeetCode 分析如果为空或者只有一个根节点不翻转否则左子树和右子树交换继续翻转左子树、右子树。
class Solution {public TreeNode invertTree(TreeNode root) {// 如果树为空或者只有一个根节点不翻转if(root null || (root.left null root.right null)) {return root;}// 否则左子树和右子树交换TreeNode tmp root.left;root.left root.right;root.right tmp;// 翻转左子树、右子树invertTree(root.left);invertTree(root.right);return root;}
}
6.5、判断平衡二叉树
110. 平衡二叉树 - 力扣LeetCode
平衡二叉树每一棵子树的左右子树的高度差不超过1。
分析空树是平衡二叉树。左子树是平衡二叉树且右子树是平衡二叉树左子树的高度和右子树的高度差的绝对值≤1是平衡二叉树否则不是。
时间复杂度O(N^2)对于树中每个结点都要求其左、右子树的高度每次求子树高度都会遍历整棵子树。
class Solution {public int height(TreeNode root) {if (root null) { // 空树深度为0return 0;}return Math.max(height(root.left), height(root.right)) 1;}public boolean isBalanced(TreeNode root) {// 空树是平衡二叉树if(root null) {return true;}// 左子树不是平衡二叉树或者右子树不是平衡二叉树则树不是平衡二叉树if(!isBalanced(root.left) || !isBalanced(root.right)) {return false;}// 左右子树高度差的绝对值≤1是平衡二叉树否则不是return Math.abs(height(root.left) - height(root.right)) 1;}
}
改进其实求树的高度就包含了求子树的高度但是上面的代码重复求了子树的高度。改进思路就是我们只需求一次树的高度在此过程中必然历经求子树、子子树高度在求到它们高度的之后马上判断它们的高度差的绝对值是否≤1它们是否是平衡二叉树。
时间复杂度O(N)。只求了一次树的高度遍历了所有结点。
class Solution {/*** 返回值-1 表示不为平衡二叉树大于 -1 表示树的高度。*/private int height(TreeNode root) {if (root null) { // 空树深度为0return 0;}// 求左、右子树高度int leftH height(root.left);int rightH height(root.right);// 求完高度马上判断是否符合平衡二叉树的要求// 左、右子树是否为平衡二叉树if(leftH -1 || rightH -1) {return -1;}// 左右子树高度差是否符合要求if(Math.abs(leftH - rightH) 1) {return -1;}// 左、右子树符合平衡二叉树要求返回树的高度return Math.max(leftH, rightH) 1;}public boolean isBalanced(TreeNode root) {// 空树是平衡二叉树if(root null) {return true;}// 如果返回值 -1表示是树高度是平衡二叉树否则不是return height(root) -1;}
}
6.6、判断对称二叉树
101. 对称二叉树 - 力扣LeetCode 分析子问题思路。空树对称。非空树对于左、右子树根节点都为空则对称一个为空、一个不为空则不对称都不为空但是值不相等则不对称都不为空且值相等左根的左子树与右根的右子树对称且左根的右子树与右根的左子树对称则树对称否则不对称。
class Solution {public boolean isSymmetric(TreeNode root) {if(root null) { // 空树对称return true;}return isSymmetricChild(root.left, root.right);}public boolean isSymmetricChild(TreeNode leftRoot, TreeNode rightRoot) {// 左根、右根都为空对称if(leftRoot null rightRoot null) {return true;}// 左、右根其中一个不为空另一个为空不对称if((leftRoot null rightRoot ! null) || (leftRoot ! null rightRoot null)) {return false;}// 左右根不为空但值不等不对称if(leftRoot ! null rightRoot ! null leftRoot.val ! rightRoot.val) {return false;}// 左根的左子树、右根的右子树对称且左根的右子树、右根的左子树对称才对称return isSymmetricChild(leftRoot.left, rightRoot.right) isSymmetricChild(leftRoot.right, rightRoot.left);}
}
6.7、先序构建中序遍历
二叉树遍历_牛客题霸_牛客网 分析重点在根据先序遍历序列构建二叉树。因为这里告诉了空结点所以只有一个先序遍历序列也能构建二叉树。 遍历思想。先序遍历如果根节点是#则返回 null如果根节点不是#则创建结点到下一个字符创建左子树、创建右子树最后返回根节点。 import java.util.Scanner;class TreeNode {char value;TreeNode left;TreeNode right;public TreeNode(char value) {this.value value;}
}public class Main {public static int i; // 记录字符下标// 先序创建树public static TreeNode createTree(String str) {TreeNode root null;if (str.charAt(i) ! #) {root new TreeNode(str.charAt(i)); // 创建新节点i;// 创建左、右子树root.left createTree(str);root.right createTree(str);} else {i;}return root;}// 中序遍历public static void inOrder(TreeNode root) {if (root null) {return;}inOrder(root.left);System.out.print(root.value );inOrder(root.right);}public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNextLine()) {String str in.nextLine();i 0;TreeNode root createTree(str);inOrder(root);}}
}
6.8、最近公共祖先
236. 二叉树的最近公共祖先 - 力扣LeetCode 分析根据题目树中必有p、q两节点。如果 p 在左子树中q 在右子树中则 root 为最近公共祖先。 如果 p、q 中存在一个是根结点则 root 为最近公共祖先。 如果 p、q 都在左子树中进入左子树找最近公共祖先。 如果 p、q 都在右子树中进入右子树找最近公共祖先。 时间复杂度O(N)
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 如果为空树没有最近公共祖先// 必须加此判断遇到叶子结点递归函数才能返回 nullif(root null) {return null;}// 其中一个是根节点最近公共祖先是根if(p root || q root) {return root;}TreeNode leftFather lowestCommonAncestor(root.left, p, q);TreeNode rightFather lowestCommonAncestor(root.right, p, q);// p、q 分布在左、右两子树中最近公共祖先是根if(leftFather ! null rightFather ! null) {return root;}// 最近公共祖先在左子树中if(leftFather ! null) {return leftFather;}// 最近公共祖先在右子树中if(rightFather ! null) {return rightFather;}// 树中不存在 q、preturn null;}
}
思路2找到根节点分别到 p、q 的路径对比路径找到最近公共祖先。 p 的路径3、5、6。size3
q 的路径3、5、2、4。size4
q 路径出栈 4-31 个元素得到 3、5、2。
p 、q 同时出栈不相同则继续同时出栈相同则找到最近公共祖先。
时间复杂度O(N^2)找了两次路径。
class Solution {public boolean getPath(TreeNode root, TreeNode target, StackTreeNode stack) {if(root null) { // 空树没有路径return false;}stack.push(root); // 根节点入栈if(root target) { // 找到目标节点退出return true;}boolean found getPath(root.left, target, stack); // 在左子树中寻找路径if(found) { // 找到路径退出return true;}found getPath(root.right, target, stack); // 在右子树中寻找路径if(found) { // 找到路径退出return true;}stack.pop(); // 路径没找到根结点出栈return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {StackTreeNode stack new Stack();StackTreeNode stack2 new Stack();getPath(root, p, stack); // 寻找 p 的路径getPath(root, q, stack2); // 寻找 q 的路径// 计算路径长度差长的路径先出栈差的绝对值长度int len stack.size() - stack2.size();if(len 0) { // 长度差为负交换两个栈StackTreeNode temp stack;stack stack2;stack2 temp;len -len;}// 弹出栈中元素直到长度差为0while(len-- ! 0) {stack.pop();}// 弹出栈中元素不相同则继续弹相同则为最近公共祖先while(!stack.isEmpty() !stack2.isEmpty() stack.peek() ! stack2.peek()) {stack.pop();stack2.pop();}return stack.isEmpty()? null : stack.peek(); // 栈为空没有最近公共祖先}
}
6.9、根据前序、中序构造树
105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode 分析前序遍历从左往右找根节点创建根节点。再在中序遍历中找根节点的位置区分左右子树。再构建左子树构建右子树。
class Solution {private int preIndex; // 先序序列的根下标public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTree(preorder, inorder, 0, inorder.length-1);}private int findIndex(int[] inorder, int low, int high, int rootVal) {for(int i low; i high; i) {if(inorder[i] rootVal) {return i;}}return -1;}// low、high 为在中序序列中子树的起始、终止下标private TreeNode buildTree(int[] preorder, int[] inorder, int low, int high) {if(low high) { // 没有结点了返回空return null;}int rootVal preorder[preIndex]; // 根TreeNode root new TreeNode(rootVal); // 创建根结点preIndex;int inIndex findIndex(inorder, low, high, rootVal); // 在中序序列中找根的位置// 构建左、右子树root.left buildTree(preorder, inorder, low, inIndex-1);root.right buildTree(preorder, inorder, inIndex1, high);return root;}
}
6.10、根据中序、后序遍历构造树
106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode
分析方法与 6.9 大致相同只不过后序序列是从后往前遍历根。后序左右根倒着遍历会先创建右子树。
class Solution {private int postIndex; // 后序序列的根下标public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex postorder.length-1;return buildTree(postorder, inorder, 0, inorder.length-1);}private int findIndex(int[] inorder, int low, int high, int rootVal) {for(int i low; i high; i) {if(inorder[i] rootVal) {return i;}}return -1;}// low、high 为在中序序列中子树的起始、终止下标private TreeNode buildTree(int[] postorder, int[] inorder, int low, int high) {if(low high) { // 没有结点了返回空return null;}int rootVal postorder[postIndex]; // 根TreeNode root new TreeNode(rootVal); // 创建根结点postIndex--;int inIndex findIndex(inorder, low, high, rootVal); // 在中序序列中找根的位置// 构建左、右子树root.right buildTree(postorder, inorder, inIndex1, high);root.left buildTree(postorder, inorder, low, inIndex-1);return root;}
}
6.11、根据二叉树创建字符串 分析前序遍历同一棵子树中的结点会被()包在一起。空树不打印。非空树打印根节点如果左右孩子都为空什么都不打印。如果左孩子不为空右孩子为空打印(遍历左子树打印)。如果左孩子为空右孩子不为空打印()(遍历右子树打印)。如果左右孩子都不为空打印(遍历左子树打印)(遍历右子树打印)。
class Solution {public String tree2str(TreeNode root) {StringBuilder str new StringBuilder();tree2str(root, str);return str.toString();}public void tree2str(TreeNode root, StringBuilder str) {// 空树不打印if (root null) {return;}str.append(root.val); // 打印根节点// 如果左孩子不为空打印(遍历左子树打印)if (root.left ! null) {str.append(();tree2str(root.left, str);str.append());// 如果右孩子为空什么都不打印// 如果右孩子不为空打印(遍历右子树打印)// if(root.right ! null) {// str.append(();// tree2str(root.right, str);// str.append());// }} else {// 如果右子树为空什么都不打印// 如果右子树不为空打印()打印(遍历右子树打印)if (root.right ! null) {str.append(());// str.append(();// tree2str(root.right, str);// str.append());}}if (root.right ! null) {str.append(();tree2str(root.right, str);str.append());}}
}
