网站轮播图片怎么做,网站建设中 提示,徐州网站开发服务,网站建设叁金手指花总91. 概述
二叉树是这么一种树状结构#xff1a;每个节点最多有两个孩子#xff0c;左孩子和右孩子
完全二叉树#xff1a;是一种二叉树结构#xff0c;除了最后一层以外#xff0c;每一层都必须填满#xff0c;填充时要遵循从左到右
平衡二叉树#xff1a;是一种二叉树…1. 概述
二叉树是这么一种树状结构每个节点最多有两个孩子左孩子和右孩子
完全二叉树是一种二叉树结构除了最后一层以外每一层都必须填满填充时要遵循从左到右
平衡二叉树是一种二叉树结构其中每个节点的左右子树高度相差不超过1 2. 存储
存储方式分为两种:
①定义树结点与左、右孩子引用TreeNode
②使用数组若用0作为树的根节点索引可以通过以下方式计算
父 floor((子 - 1) / 2)左孩子 父 * 2 1右孩子 父 * 2 2 3. 遍历
遍历方式也分为两种
①广度优先遍历尽可能先访问距离根节点最近的节点也称为层序遍历
②深度优先遍历对于二叉树可以进一步划分为三种要深入到叶子节点
pre-order前序遍历对于每一棵子树先访问该节点然后是左子树最后是右子树in-order中序遍历对于每一棵子树先访问左子树然后是该节点最后是右子树post-order后续遍历对于每一棵子树先访问左子树然后是右子树最后是该节点 3.1 广度优先遍历 本轮开始时队列本轮访问节点[1]1[2, 3]2[3, 4]3[4, 5, 6]4[5, 6]5[6, 7, 8]6[7, 8]7[8]8[]
1. 初始化将根节点加入队列
2. 循环处理队列中每个节点直至队列为空
3. 每次循环内处理节点后将它的孩子节点即下一层节点加入队列
注意
以上用队列来实现层序遍历是针对TreeNode这种方式表示的二叉树对于数组实现的二叉树则直接遍历数组即可自然为层序遍历的顺序 3.2 深度优先遍历 栈暂存已处理前序遍历中序遍历[1]1 ✔️ 左 右1[1, 2]2✔️ 左 右 1✔️ 左 右2[1, 2, 4]4✔️ 左✔️ 右✔️ 2✔️ 左 右 1✔️ 左 右44[1, 2]2✔️ 左✔️ 右✔️ 1✔️ 左 右2[1]1✔️ 左✔️ 右1[1, 3]3✔️ 左 右 1✔️ 左✔️ 右3[1, 3, 5]5✔️ 左✔️ 右✔️ 3✔️ 左 右 1✔️ 左✔️ 右55[1, 3]3✔️ 左✔️ 右 1✔️ 左✔️ 右3[1, 3, 6]6✔️ 左✔️ 右✔️ 3✔️ 左✔️ 右 1✔️ 左✔️ 右66[1, 3]3✔️ 左✔️ 右✔️ 1✔️ 左✔️ 右[1]1✔️ 左✔️ 右✔️[] 3.2.1 递归实现
/*** h3前序遍历/h3* param node 节点*/
static void preOrder(TreeNode node) {if (node null) {return;}System.out.print(node.val \t); // 值preOrder(node.left); // 左preOrder(node.right); // 右
}/*** h3中序遍历/h3* param node 节点*/
static void inOrder(TreeNode node) {if (node null) {return;}inOrder(node.left); // 左System.out.print(node.val \t); // 值inOrder(node.right); // 右
}/*** h3后序遍历/h3* param node 节点*/
static void postOrder(TreeNode node) {if (node null) {return;}postOrder(node.left); // 左postOrder(node.right); // 右System.out.print(node.val \t); // 值
} 3.2.2 非递归实现
前序遍历
LinkedListStackTreeNode stack new LinkedListStack(); // 此处的LinkedListStack为自己实现的
TreeNode curr root;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);System.out.println(curr);curr curr.left;} else {TreeNode pop stack.pop();curr pop.right;}}
中序遍历
LinkedListStackTreeNode stack new LinkedListStack();
TreeNode curr root;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);curr curr.left;} else {TreeNode pop stack.pop();System.out.println(pop);curr pop.right;}
}
后序遍历
LinkedListStackTreeNode stack new LinkedListStack();
TreeNode curr root;
TreeNode pop null;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);curr curr.left;} else {TreeNode peek stack.peek();if (peek.right null || peek.right pop) {pop stack.pop();System.out.println(pop);} else {curr peek.right;}}
}
对于后序遍历向后走时需要处理完右子树才能pop出栈。如何直到右子树处理完成呢
①如果栈顶元素的 right null 表示没啥可处理的可以出栈
②如果栈顶元素的 right ! null
那么使用lastPop记录最近出栈的节点即表示从这个节点向回走如果栈顶元素 right lastPop此时应当出栈
对于前、中两种遍历实际以上代码从右子树向回走时并未走完全程stack提前出栈了而后序遍历以上代码是走完全程了。 统一写法依据后序遍历修改
LinkedListTreeNode stack new LinkedList();TreeNode curr root; // 代表当前节点
TreeNode pop null; // 最近一次弹栈的元素
while (curr ! null || !stack.isEmpty()) {if (curr ! null) {colorPrintln(前: curr.val, 31);stack.push(curr); // 压入栈为了记住回来的路curr curr.left;} else {TreeNode peek stack.peek();// 右子树可以不处理, 对中序来说, 要在右子树处理之前打印if (peek.right null) {colorPrintln(中: peek.val, 36);pop stack.pop();colorPrintln(后: pop.val, 34);}// 右子树处理完成, 对中序来说, 无需打印else if (peek.right pop) {pop stack.pop();colorPrintln(后: pop.val, 34);}// 右子树待处理, 对中序来说, 要在右子树处理之前打印else {colorPrintln(中: peek.val, 36);curr peek.right;}}
}public static void colorPrintln(String origin, int color) {System.out.printf(\033[%dm%s\033[0m%n, color, origin);
}
一张图演示三种遍历 红色前序遍历绿色中序遍历蓝色后序遍历 4. 习题
4.1 前序遍历二叉树
给你二叉树的根节点 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) {ListInteger result new ArrayList();preorderHelper(root, result);return result;}private void preorderHelper(TreeNode root, ListInteger result) {if (root null) {return;}result.add(root.val);preorderHelper(root.left, result);preorderHelper(root.right, result);}
}
解法二迭代
/*** 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();ListInteger result new ArrayList();TreeNode curr root;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);result.add(curr.val);curr curr.left;} else {TreeNode pop stack.pop();curr pop.right;}}return result;}
}
解法三莫里斯遍历Morris Traversal
①莫里斯遍历的核心思想是通过利用树的空指针链接来避免使用栈
②对于每个节点如果它的左子树为空则访问当前节点并移动到右子树
③如果左子树不为空找到当前节点的前驱节点即左子树中最右的节点检查它的右指针
如果它的右指针为空则将其指向当前节点并返回当前节点如果它的右指针已经指向当前节点说明左子树已经遍历结束将右指针恢复为null并移动到右子树。
时间复杂度O(n)空间复杂度O(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 { public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); TreeNode curr root; while (curr ! null) { if (curr.left null) { // 访问当前节点 result.add(curr.val); curr curr.right; // 移动到右子树 } else { // 找到当前节点的前驱节点 TreeNode pred curr.left; while (pred.right ! null pred.right ! curr) { pred pred.right; } // 建立链接 if (pred.right null) { pred.right curr; // 建立临时连接 result.add(curr.val); // 访问当前节点 curr curr.left; // 移动到左子树 } else { // 恢复树结构 pred.right null; curr curr.right; // 移动到右子树 } } } return result; }
} 4.2 中序遍历二叉树
给定一个二叉树的根节点 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) {ListInteger result new ArrayList();inorderHelper(root, result);return result;}private void inorderHelper(TreeNode root, ListInteger result) {if (root null) {return;}inorderHelper(root.left, result);result.add(root.val);inorderHelper(root.right, result);}
}
解法二迭代
/*** 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();ListInteger result new ArrayList();TreeNode curr root;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);curr curr.left;} else {TreeNode pop stack.pop();result.add(pop.val);curr pop.right;}}return result;}
}
解法三莫里斯算法
①莫里斯遍历的核心思想是通过利用树的空指针链接来避免使用栈
②对于每个节点如果它的左子树为空则访问当前节点并移动到右子树
③如果左子树不为空找到当前节点的前驱节点即左子树中最右的节点检查它的右指针
如果它的右指针为空则将其指向当前节点并返回当前节点如果它的右指针已经指向当前节点说明左子树已经遍历结束将右指针恢复为null并移动到右子树。
/*** 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) {ListInteger result new ArrayList();TreeNode curr root;while (curr ! null) {if (curr.left null) { // 左子树为空// 访问当前节点result.add(curr.val);// 移动到右子树curr curr.right;} else {// 找到当前节点的前驱节点TreeNode pred curr.left;while (pred.right ! null pred.right ! curr) {pred pred.right;}// 建立链接if (pred.right null) {// 建立临时链接pred.right curr;// 移动到左子树curr curr.left;} else {// 恢复树结构pred.right null;// 访问当前节点result.add(curr.val);// 移动到右子树curr curr.right;}}}return result;}
} 4.3 后序遍历二叉树
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例 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) {ListInteger result new ArrayList();postOrderHelper(root, result);return result;}private void postOrderHelper(TreeNode root, ListInteger result) {if (root null) {return;}postOrderHelper(root.left, result);postOrderHelper(root.right, result);result.add(root.val);}
}
解法二迭代
/*** 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();ListInteger result new ArrayList();TreeNode curr root;TreeNode pop null;while (!stack.isEmpty() || curr ! null) {if (curr ! null) {stack.push(curr);curr curr.left;} else {TreeNode peek stack.peek();if (peek.right null || peek.right pop) {pop stack.pop();result.add(pop.val);} else {curr peek.right;}}}return result;}
} 4.4 对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。
示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false提示
树中节点数目在范围 [1, 1000] 内-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 boolean isSymmetric(TreeNode root) {if(root null) {return true;}return dfs(root.left, root.right);}private boolean dfs(TreeNode left, TreeNode right) {if(left null right null) {return true;} if(left null || right null) {return false;}return (left.val right.val) dfs(left.left, right.right) dfs(left.right, right.left);}
}
解法二迭代
/*** 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 boolean isSymmetric(TreeNode root) {if (root null) {return true;}QueueTreeNode queue new LinkedList();queue.offer(root.left);queue.offer(root.right);while (!queue.isEmpty()) {TreeNode leftNode queue.poll();TreeNode rightNode queue.poll();if (leftNode null rightNode null) { // 左右两个子树为空continue;}if (leftNode null || rightNode null) { // 两边只有一个子树为空return false;}if (leftNode.val ! rightNode.val) {return false;}queue.offer(leftNode.left);queue.offer(rightNode.right);queue.offer(leftNode.right);queue.offer(rightNode.left);}return true;}
} 4.5 二叉树最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1 输入root [3,9,20,null,null,15,7]
输出3示例 2
输入root [1,null,2]
输出2提示
树中节点的数量在 [0, 10^4] 区间内。-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 int maxDepth(TreeNode root) {if (root null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) 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 {public int maxDepth(TreeNode root) {if (root null) {return 0;}StackPairTreeNode, Integer stack new Stack();stack.push(new Pair(root, 1));int maxDepth 0;while (!stack.isEmpty()) {PairTreeNode, Integer current stack.pop();TreeNode node current.getKey();int depth current.getValue();maxDepth Math.max(depth, maxDepth);if (node.left ! null) {stack.push(new Pair(node.left, depth 1));}if (node.right ! null) {stack.push(new Pair(node.right, depth 1));}}return maxDepth;}
}
解法三使用二叉树的非递归后序遍历栈的最大高度即为最大深度
/*** 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 maxDepth(TreeNode root) {TreeNode curr root;TreeNode pop null;LinkedListTreeNode stack new LinkedList();int max 0; // 栈的最大高度while(curr ! null || !stack.isEmpty()) {if(curr ! null) {stack.push(curr);max Integer.max(stack.size(), max);curr curr.left;} else {TreeNode peek stack.peek();if(peek.right null || peek.right pop) {pop stack.pop();} else {curr peek.right;}}}return max;}
}
解法四二叉树的层序遍历层数即最大深度
/*** 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 maxDepth(TreeNode root) {if (root null) {return 0;}QueueTreeNode queue new LinkedList();queue.offer(root);int depth 0;while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {TreeNode poll queue.poll();if (poll.left ! null) {queue.offer(poll.left);}if (poll.right ! null) {queue.offer(poll.right);}}depth;}return depth;}
} 4.6 二叉树最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出2示例 2
输入root [2,null,3,null,4,null,5,null,6]
输出5提示
树中节点数的范围在 [0, 10^5] 内-1000 Node.val 1000
解法一层序遍历。遇到第一个叶子节点所在层数即为最小深度
/*** 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 minDepth(TreeNode root) {if (root null) {return 0;}QueueTreeNode queue new LinkedList();queue.offer(root);int depth 1;while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {TreeNode node queue.poll();if (node.left null node.right null) {return depth;}if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}depth;}return depth;}
}
解法二后序遍历
相较于求最大深度应当考虑
当右子树为null应当返回左子树深度加一当左子树为null应当返回右子树深度加一
/*** 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 minDepth(TreeNode node) {if (node null) {return 0;}int d1 minDepth(node.left);int d2 minDepth(node.right);if (d1 0 || d2 0) {return d1 d2 1;}return Integer.min(d1, d2) 1;}
} 4.7 翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
示例 1
输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2
输入root [2,1,3]
输出[2,3,1]示例 3
输入root []
输出[]提示
树中节点数目范围在 [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 TreeNode invertTree(TreeNode root) {reverse(root);return root;}private void reverse(TreeNode node) {if(node null) {return;}TreeNode t node.left;node.left node.right;node.right t;reverse(node.left);reverse(node.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 {public TreeNode invertTree(TreeNode root) {if(root null) {return null;}// 递归翻转左右子树TreeNode left invertTree(root.left);TreeNode right invertTree(root.right);// 交换左右子树// TreeNode t root.left;root.left root.right;root.right left;return root;}
} 4.8 后缀表达式转二叉树
遇到运算符则出栈两次将出栈元素与当前节点建立父子关系当前节点入栈遇到数字则入栈 public TreeNode constructExpressionTree(String[] tokens) {LinkedListTreeNode stack new LinkedList();for (String token : tokens) {switch (token) {// 遇到运算符出栈两次与当前节点建立父子关系将当前节点入栈case , -, *, / - {TreeNode right stack.pop();TreeNode left stack.pop();TreeNode parent new TreeNode(Integer.parseInt(token));parent.left left;parent.right right;stack.push(parent);}default - { // 遇到数字入栈stack.push(new TreeNode(Integer.parseInt(token)));}}}return stack.peek();} 4.9 根据前序与中序遍历结果构造二叉树
给定两个整数数组 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 保证 为二叉树的中序遍历序列
解法一
先通过前序遍历结果定位根节点再结合中序遍历结果切分左右子树
/*** 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) {MapInteger, Integer indexMap new HashMap();for (int i 0; i inorder.length; i) {indexMap.put(inorder[i], i);}return buildTreeHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, indexMap);}private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd,MapInteger, Integer indexMap) {if (preStart preEnd || inStart inEnd) {return null;}int rootVal preorder[preStart]; // 根节点的位置TreeNode root new TreeNode(rootVal);int inIndex indexMap.get(rootVal);int leftSubtreeSize inIndex - inStart; // 左子树root.left buildTreeHelper(preorder, inorder, preStart 1, preStart leftSubtreeSize, inStart, inIndex - 1,indexMap);root.right buildTreeHelper(preorder, inorder, preStart leftSubtreeSize 1, preEnd, inIndex 1, inEnd,indexMap);return root;}
} 4.10 根据中序与后序遍历结果构造二叉树
解法一
先通过后序遍历结果定位根节点再结合中序遍历结果划分左右子树
/*** 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) {MapInteger, Integer indexMap new HashMap();for (int i 0; i inorder.length; i) {indexMap.put(inorder[i], i);}return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, indexMap);}private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd,MapInteger, Integer indexMap) {if (inStart inEnd || postStart postEnd) {return null;}int rootVal postorder[postEnd]; // 根节点的位置TreeNode root new TreeNode(rootVal);int inIndex indexMap.get(rootVal);int rightSubtreeSize inEnd - inIndex; // 右子树root.left buildTreeHelper(inorder, postorder, inStart, inIndex - 1, postStart, postEnd - rightSubtreeSize - 1,indexMap);root.right buildTreeHelper(inorder, postorder, inIndex 1, inEnd, postEnd - rightSubtreeSize, postEnd - 1,indexMap);return root;}
}
