晚上下班再补充
- 重建二叉树
思路很简单，过程很绕，换句话说结果容易错
public class Solution0526 {
static HashMap<Integer,Integer> arrl = new HashMap<>();
public static TreeNode rebulid(int[] pre,int[] ino) {
for(int i=0;i<ino.length;i++) {
arrl.put(ino[i], i);
}
return rebulidcore(pre,0,pre.length-1,ino,0,ino.length-1);
}
public static TreeNode rebulidcore(int[] pre,int pleft,int pright,int[] ino,int ileft,int iright) {
if(pleft>pright) return null;
int index = arrl.get(pre[pleft]);
int treesize = index-ileft;
TreeNode root = new TreeNode(pre[pleft]);
//记得给左右树赋值
root.left = rebulidcore(pre,pleft+1,pleft+treesize,ino,ileft,ileft+treesize-1);
root.right =rebulidcore(pre,pleft+treesize+1,pright,ino,ileft+treesize+1,iright);
return root;
}
public static void main(String[] args) {
int[] preorder = {3,9,20,15,7};
int[] inorder = {9,3,15,20,7};
TreeNode root2 = rebulid(preorder,inorder);
System.out.println(root2.right.left);
}
}
- 二叉树的下一个结点
一直疑惑的是算法给的next节点是个什么鬼
① 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；
② 否则，向上找第一个左链接指向的树包含该节点的祖先节点。
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode.right != null) {
TreeLinkNode node = pNode.right;
while (node.left != null)
node = node.left;
return node;
} else {
while (pNode.next != null) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode)
return parent;
pNode = pNode.next;
}
}
return null;
}
- 用两个栈实现队列
Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();
public void push(int node) {
in.push(node);
}
public int pop() throws Exception {
if (out.isEmpty())
while (!in.isEmpty())
out.push(in.pop());
if (out.isEmpty())
throw new Exception("queue is empty");
return out.pop();
}
