106. 从中序与后序遍历序列构造二叉树
class Solution {Map<Integer, Integer> inOrderIndex = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder.length == 0 || postorder.length == 0) return null;// 做一次遍历，记录中序遍历的索引for (int i = 0; i < inorder.length; i++) {inOrderIndex.put(inorder[i], i);}int inStart = 0;int inEnd = inorder.length;int poStart = 0;int poEnd = postorder.length;return rebuildTree(inorder, postorder, inStart, inEnd, poStart, poEnd);}private TreeNode rebuildTree(int[] inorder, int[] postorder, int inStart, int inEnd, int poStart, int poEnd) {if (poStart == poEnd) return null;int rootValue = postorder[poEnd - 1];TreeNode root = new TreeNode(rootValue);int delimiter = inOrderIndex.get(rootValue);int leftInOrderStart = inStart;int leftInOrderEnd = delimiter;int rightInOrderStart = delimiter + 1;int rightInOrderEnd = inEnd;int leftPostOrderStart = poStart;// 左子树后序终止索引int leftPostOrderEnd = poStart + delimiter - inStart;int rightPostOrderStart = poStart + (delimiter - inStart) ;int rightPostOrderEnd = poEnd - 1;root.left = rebuildTree(inorder, postorder, leftInOrderStart, leftInOrderEnd, leftPostOrderStart, leftPostOrderEnd);root.right = rebuildTree(inorder, postorder, rightInOrderStart, rightInOrderEnd, rightPostOrderStart, rightPostOrderEnd);return root;}}
思路和通过前序和中序遍历构造二叉树思路类似。
This is my iterative solution, think about “Constructing Binary Tree from inorder and preorder array”, the idea is quite similar. Instead of scanning the preorder array from beginning to end and using inorder array as a kind of mark, in this question, the key point is to scanning the postorder array from end to beginning and also use inorder array from end to beginning as a mark because the logic is more clear in this way. The core idea is: Starting from the last element of the postorder and inorder array, we put elements from postorder array to a stack and each one is the right child of the last one until an element in postorder array is equal to the element on the inorder array. Then, we pop as many as elements we can from the stack and decrease the mark in inorder array until the peek() element is not equal to the mark value or the stack is empty. Then, the new element that we are gonna scan from postorder array is the left child of the last element we have popped out from the stack.
关键点：
- postorder 从后往前扫描。
- 使用inorder
从 postorder 和 inorder 数组的最后一个元素开始遍历。将 postorder 数组的元素放入栈中，直到和 inorder 数组相等为止。然后
public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder.length == 0 || postorder.length == 0) return null;int ip = inorder.length - 1;int pp = postorder.length - 1;Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode prev = null;TreeNode root = new TreeNode(postorder[pp]);stack.push(root);pp--;while (pp >= 0) {while (!stack.isEmpty() && stack.peek().val == inorder[ip]) {prev = stack.pop();ip--;}TreeNode newNode = new TreeNode(postorder[pp]);if (prev != null) {prev.left = newNode;} else if (!stack.isEmpty()) {TreeNode currTop = stack.peek();currTop.right = newNode;}stack.push(newNode);prev = null;pp--;}return root;}
105. 从前序与中序遍历序列构造二叉树
遍历方法基于以下判断：
对于前序遍历中的任意两个连续节点 
和 
%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=v&id=jRAQq)，根据前序遍历的流程，我们可以知道 
和 %22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=v&id=klaGa) 只有两种可能的关系：
- %22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=v&id=z4Llf) 是
的左儿子。这是因为在遍历到 
之后，下一个遍历的节点就是 
的左儿子，即 %22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=v&id=Bf57a)。 
没有左儿子。并且%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=v&id=Wo5C2)是
的某个祖先节点（或者
本身）的右儿子。如果
没有左儿子，那么下一个遍历的节点就是
的右儿子。如果
没有右儿子，我们就会向上回溯，直到遇到第一个有右儿子（且
不在它的右儿子的子树中）的节点
，那么 %22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-76%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=v&id=WS6M2) 就是 
的右儿子。
在遍历前序数组中，我们会遇到以下问题：
- 下一个节点是左子树还是右子树。这需要和中序数组对比确认，如果相等，就为右子树，如果不相等，则为左子树。
- 如果遇到和中序数组首个元素相等的节点，说明前序数组的下一个元素就不再是左节点而右节点了。那这个节点到底是哪个节点的右节点呢?
3/9/20
public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder.length == 0) return null;Stack<TreeNode> s = new Stack<>();TreeNode root = new TreeNode(preorder[0]);TreeNode cur = root;// j指针指向中序数组，int j = 0;// 遍历前序数组，中序数组是用来辅助判断右节点for (int i = 1; i < preorder.length; i++) {if (cur.val != inorder[j]) {// 前序指针指向的元素和中序j的不相等，// 说明当前preorder[i]是前面节点cur的左节点cur.left = new TreeNode(preorder[i]);// 将cur压入栈s.push(cur);// 更新cur指针，指向left，接下来构建cur.left节点cur = cur.left;} else {// 遇到相等j++;// 别忘记这里还还需要peek一次while (!s.empty() && s.peek().val == inorder[j]) {cur = s.pop();j++;}cur = cur.right = new TreeNode(preorder[i]);}}return root;}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// deal with edge case(s)
if (preorder.length == 0) {
return null;
}
// build a map of the indices of the values as they appear in the inorder array
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// initialize the stack of tree nodes
Stack<TreeNode> stack = new Stack<>();
int value = preorder[0];
TreeNode root = new TreeNode(value);
stack.push(root);
// for all remaining values...
for (int i = 1; i < preorder.length; i ++) {
// create a node
value = preorder[i];
TreeNode node = new TreeNode(value);
if (map.get(value) < map.get(stack.peek().val)) {
// the new node is on the left of the last node,
// so it must be its left child (that's the way preorder works)
stack.peek().left = node;
} else {
// the new node is on the right of the last node,
// so it must be the right child of either the last node
// or one of the last node's ancestors.
// pop the stack until we either run out of ancestors
// or the node at the top of the stack is to the right of the new node
TreeNode parent = null;
while(!stack.isEmpty() && map.get(value) > map.get(stack.peek().val)) {
parent = stack.pop();
}
parent.right = node;
}
stack.push(node);
}
return root;
}
}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// deal with edge case(s)
if (preorder.length == 0) {
return null;
}
// build a map of the indices of the values as they appear in the inorder array
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// initialize the stack of tree nodes
Stack<TreeNode> stack = new Stack<>();
int value = preorder[0];
TreeNode root = new TreeNode(value);
stack.push(root);
// for all remaining values...
for (int i = 1; i < preorder.length; i ++) {
// create a node
value = preorder[i];
TreeNode node = new TreeNode(value);
if (map.get(value) < map.get(stack.peek().val)) {
// the new node is on the left of the last node,
// so it must be its left child (that's the way preorder works)
stack.peek().left = node;
} else {
// the new node is on the right of the last node,
// so it must be the right child of either the last node
// or one of the last node's ancestors.
// pop the stack until we either run out of ancestors
// or the node at the top of the stack is to the right of the new node
TreeNode parent = null;
while(!stack.isEmpty() && map.get(value) > map.get(stack.peek().val)) {
parent = stack.pop();
}
parent.right = node;
}
stack.push(node);
}
return root;
}
}
public TreeNode buildTree_1(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.length; i++) {
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else {
// 这里还要再peek()一次
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
530. 二叉搜索树的最小绝对差
思路：中序遍历
class Solution {
public int getMinimumDifference(TreeNode root) {
int res = Integer.MAX_VALUE;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode prev = null;
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
while (p != null) {
stack.addLast(p);
p = p.left;
}
TreeNode node = stack.pollLast();
if (prev != null && (Math.abs(node.val - prev.val) < res)) res = Math.abs(node.val - prev.val);
p = node.right;
prev = node;
}
return res;
}
}
236. 二叉树的最近公共祖先
代码随想录解析
解决思路很巧妙：
当遇到值相同的节点时，就返回它的根节点，并一直向上返回。返回特定值就是回溯的过程。得好好体会体会呀。
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 找到节点 if ( root == null || root.val == q.val || root.val == p.val) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; } else { return left == null ? right : left; } } }
- 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
- 在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
- 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
102. 二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
TreeNode curEnd;
TreeNode nextEnd;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> data = new LinkedList<>();
while (size > 0) {
TreeNode pop = queue.pollLast();
data.add(pop.val);
if (pop.left != null) queue.addFirst(pop.left);
if (pop.right != null) queue.addFirst(pop.right);
size--;
}
res.add(data);
}
return res;
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
levelHelper(res, root, 0);
return res;
}
private void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
if (root == null) return ;
if (height >= res.size()) {
res.add(new LinkedList<Integer>());
}
res.get(height).add(root.val);
levelHelper(res, root.left, height + 1);
levelHelper(res, root.right, height + 1);
}
}
226. 翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode n = queue.pollLast();
swap(n);
if (n.left != null) queue.addLast(n.left);
if (n.right != null) queue.addLast(n.right);
size--;
}
}
return root;
}
private void swap(TreeNode root) {
if (root == null) return ;
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
}
222. 完全二叉树的节点个数
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
if (leftH == rightH) {
// 说明左子树完整
return (1 << leftH) + countNodes(root.right);
} else {
return (1 << rightH) + countNodes(root.left);
}
}
private int getHeight(TreeNode root) {
int height = 0;
TreeNode p = root;
while (p != null) {
height++;
p = p.left;
}
return height;
}
}
404. 左叶子之和
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int left = sumOfLeftLeaves(root.left);
int right = sumOfLeftLeaves(root.right);
// 判断是否遇到了左叶子节点
int midVal = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
midVal = root.left.val;
}
return midVal + left + right;
}
}
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return root != null ? dfs(root) : 0;
}
public int dfs(TreeNode node) {
int ans = 0;
if (node.left != null) {
ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
}
if (node.right != null && !isLeafNode(node.right)) {
ans += dfs(node.right);
}
return ans;
}
public boolean isLeafNode(TreeNode node) {
return node.left == null && node.right == null;
}
}
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
return dfs(root);
}
private int dfs(TreeNode root) {
if (root == null) return 0;
int ans = 0;
// 处理左节点
if (root.left != null) {
ans += isLeaf(root.left) ? root.left.val : dfs(root.left);
}
ans += dfs(root.right);
return ans;
}
private boolean isLeaf(TreeNode root) {
if (root == null) return false;
return root.left == null && root.right == null;
}
}
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
return sumOfLeftLeaves(root.left)
+ sumOfLeftLeaves(root.right)
+ (root.left!=null && root.left.left==null && root.left.right==null ? root.left.val : 0);
}
}
108. 将有序数组转换为二叉搜索树
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
Queue<MyNode> queue = new LinkedList<>();
int left = 0;
int right = nums.length - 1;
int val = nums[left + (right - left) / 2];
TreeNode root = new TreeNode(val);
queue.offer(new MyNode(root, left, right));
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
MyNode cur = queue.poll();
int mid = cur.lb + (cur.rb - cur.lb) / 2;
if (mid != cur.lb) {
TreeNode leftChild = new TreeNode(nums[cur.lb + (mid - 1 - cur.lb) / 2]);
cur.node.left = leftChild;
queue.offer(new MyNode(leftChild, cur.lb, mid - 1));
}
if (mid != cur.rb) {
TreeNode rightChild = new TreeNode(nums[mid + 1 + (cur.rb - mid - 1) / 2]);
cur.node.right = rightChild;
queue.offer(new MyNode(rightChild, mid + 1, cur.rb));
}
}
}
return root;
}
private static class MyNode {
TreeNode node;
int lb;
int index;
int rb;
public MyNode(TreeNode n, int theLeft, int theRight) {
this.node = n;
this.lb = theLeft;
this.rb = theRight;
}
}
}
若有收获，就点个赞吧
0 人点赞
