重建二叉树
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
return reConstructBinaryTree(pre,in,0,pre.length-1,0,in.length-1);
}
private TreeNode reConstructBinaryTree(int[] pre,int[] in,
int preStart,int preEnd,
int inStart,int inEnd){
if(preStart>preEnd || inStart>inEnd){
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
int index = -1;
for(int i=inStart;i<=inEnd;i++){
if(in[i]==pre[preStart]){
index = i;
break;
}
}
root.left = reConstructBinaryTree(pre,in,
preStart+1,preStart+(index-inStart),inStart,index-1);
root.right = reConstructBinaryTree(pre,in,
preStart+(index-inStart)+1,preEnd,index+1,inEnd);
return root;
}二叉树的下一个结点
//思路：
//1、如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；
//否则，向上找第一个左链接指向的树包含该节点的祖先节点。
public TreeLinkNode GetNext(TreeLinkNode pNode){
if(pNode==null){
return null;
}
if(pNode.right!=null){
//先判断 pNode 的右子树不为 null,
//pNode 的下一个结点就是 pNode 右子树的最左结点
TreeLinkNode node = pNode.right; //pNode 的右子树
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;
}对称的二叉树
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null){
return true;
}
return isSymmetrical(pRoot.left,pRoot.right);
}
//判断 p 和 q 两棵树是否对称
private boolean isSymmetrical(TreeNode p,TreeNode q){
if(p==null && q==null){
return true;
}
if(p==null || q==null){
return false;
}
if(p.val!=q.val){
return false;
}
return isSymmetrical(p.left,q.right) &&
isSymmetrical(p.right,q.left);
}按之字形顺序打印二叉树
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot==null){
return res;
}
//queue 存储的是每一行的结点
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
int level = 0;
while(!queue.isEmpty()){
if(level==res.size()){
res.add(new ArrayList<>());
}
int num = queue.size();
while(num-->0) {
TreeNode node = queue.poll();
res.get(level).add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
if(level%2==1){
Collections.reverse(res.get(level));
}
level++;
}
return res;
}把二叉树打印成多行
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot==null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
int level=0;
while(!queue.isEmpty()){
if(level==res.size()){
res.add(new ArrayList<>());
}
int num = queue.size();
while (num-->0){
TreeNode node = queue.poll();
res.get(level).add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
level++;
}
return res;
}序列化二叉树
String Serialize(TreeNode root) {
if(root==null){
return "#";
}
return root.val+" "+Serialize(root.left)+" "+Serialize(root.right);
}
//反序列化：将字符串转化为二叉树
//注意 " " 和 "#"
private String deserializeStr;
TreeNode Deserialize(String str) {
deserializeStr=str;
return Deserialize();
}
private TreeNode Deserialize(){
if (deserializeStr.length() == 0)
return null;
int index = deserializeStr.indexOf(" ");
//TODO:
//如果 index==-1 ，说明 deserializeStr 中没有出现" "，deserializeStr 表示一个节点的值
//如果 index=!-1,说明 deserializeStr[0,index-1] 是节点值
String node = index==-1?deserializeStr:deserializeStr.substring(0, index);
deserializeStr = index == -1 ? "" : deserializeStr.substring(index + 1);
//从 " "的下一个位置开始
if("#".equals(node)){
return null;
}
int val = Integer.parseInt(node);
TreeNode root = new TreeNode(val);
root.left =Deserialize();
root.right=Deserialize();
return root;
}树的子结构
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if(root1==null || root2==null){ //注意：这里约定空树不是任意一个树的子结构
return false;
}
return HasSubtree(root1.left,root2) ||
isSubtree(root1,root2) ||
HasSubtree(root1.right,root2);
}
//判断以 root2 为根节点的树是否是以 root1 为根节点的子树。
//比如:
// 2
// /
// 4
// 是
// 2
// / \
// 4 5
// 的子树
private boolean isSubtree(TreeNode root1,TreeNode root2){
if(root2==null){ // root2 为空树是 root1 的子树
return true;
}
if(root1==null){ //显然空树没有子树
return false;
}
if(root1.val!=root2.val){
return false;
}
return isSubtree(root1.left,root2.left) &&
isSubtree(root1.right,root2.right);
}从上往下打印二叉树
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if(root==null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int num = queue.size();
while(num-->0){
TreeNode node = queue.poll();
res.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
}
return res;
}二叉树的深度
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}二叉树的最小深度
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
// 1
// /
// 2
//最小深度是 1
if(root.right==null){
return 1+minDepth(root.left);
}
// 1
// \
// 2
//的最小深度是 1
if(root.left==null){
return 1+minDepth(root.right);
}
return Math.min(minDepth(root.left),minDepth(root.right))+1;
}合并二叉树
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1==null){
return t2;
}
if(t2==null){
return t1;
}
TreeNode root=new TreeNode(t1.val+t2.val);
root.left=mergeTrees(t1.left,t2.left);
root.right=mergeTrees(t1.right,t2.right);
return root;
}二叉树的所有路径
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths=new ArrayList<>();
if(root==null){
return paths;
}
List<Integer> values=new ArrayList<>();
backtrack(root,values,paths);
return paths;
}
//values 记录从根节点到叶子节点
//paths 记录路径
private void backtrack(TreeNode root, List<Integer> values,List<String> paths){
if(root==null){
return;
}
values.add(root.val);
if(root.left==null && root.right==null){ // 到达叶子节点
paths.add(buildPath(values));
}else{
backtrack(root.left,values,paths);
backtrack(root.right,values,paths);
}
values.remove(values.size()-1);
}
private String buildPath(List<Integer> values){
StringBuilder res=new StringBuilder();
for(int i=0;i<values.size();i++){
if(i==values.size()-1){
res.append(values.get(i));
}else{
res.append(values.get(i)).append("->");
}
}
return res.toString();
}二叉树中和为某一值的路径
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> values = new ArrayList<>();
backtrack(root,target,values,res);
return res;
}
// values : 记录从根节点到叶子节点的所有路径
// paths : 存储所有可能的结果
private void backtrack(TreeNode root, int target,
ArrayList<Integer> values,
ArrayList<ArrayList<Integer>> paths) {
if (root == null) {
return;
}
values.add(root.val);
if(root.left==null && root.right==null && root.val==target){
paths.add(new ArrayList<>(values));
}else{
backtrack(root.left,target-root.val,values,paths);
backtrack(root.right,target-root.val,values,paths);
}
values.remove(values.size()-1);
}二叉树的镜像
public void Mirror(TreeNode root) {
if(root==null){
return;
}
swap(root);
Mirror(root.left);
Mirror(root.right);
}
//交换 root 的左右子树
private void swap(TreeNode root){
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}平衡二叉树
private boolean isBalanced=true;
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
height(root);
return isBalanced;
}
private int height(TreeNode root){
if(root==null){
return 0;
}
int left=height(root.left);
int right=height(root.right);
if(Math.abs(left-right)>1){
isBalanced=false;
}
return 1+Math.max(left,right);
}二叉树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// p ,q 都在左子树
if(contains(root.left,p) && contains(root.left,q)){
return lowestCommonAncestor(root.left,p,q);
}
// p，q 都在右子树
if(contains(root.right,p) && contains(root.right,q)){
return lowestCommonAncestor(root.right,p,q);
}
return root;
}
//判断以root 为根节点二叉树是否包含 p 节点
private boolean contains(TreeNode root,TreeNode p){
if(root==null || p==null){
return false;
}
if(root.val == p.val){
return true;
}
return contains(root.left,p) || contains(root.right,p);
}//思路二：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
//如果 p或者是q是根节点，那么该root就是他们最近的公共父节点
if(p== root || q==root){
return root;
}
// 1
// / \
// 2 3
// 其中 p 为 2，q 为 3 则 left=p,right=q
//显然 root 为 p、q 的最近公共祖先
//p，q 在左子树中是否有公共父节点
TreeNode left = lowestCommonAncestor(root.left,p,q);
//p，q 在右子树中是否有公共父节点
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!=null && right!=null){
return root;
}
if(left != null){
return left;
}
if(right != null){
return right;
}
return null;
}二叉搜索树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(p.val<root.val && q.val<root.val){
return lowestCommonAncestor(root.left,p,q);
}
if(p.val>root.val && q.val>root.val){
return lowestCommonAncestor(root.right,p,q);
}
return root;
}二叉搜索树的第 k 个结点
//思路：
//利用二次搜索树的中序遍历性质
private TreeNode res;
private int cnt;
TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot==null){
return null;
}
inOrder(pRoot,k);
return res;
}
private void inOrder(TreeNode pRoot,int k){
if(pRoot==null){
return;
}
inOrder(pRoot.left,k);
cnt++;
if(cnt==k){
res = pRoot;
return;
}
inOrder(pRoot.right,k);
}二叉搜索树的后序遍历序列
//思路一：
//先假设该后续遍历序列可以构成二叉树
//对题目中后序遍历序列进行排序即可获取中序遍历序列
//然后根据中序遍历序列和后序遍历序列构造二叉树
//如果构造失败，返回 false
//如果构造成功，返回 true
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null || sequence.length==0){
return false;
}
int[] post = Arrays.copyOf(sequence,sequence.length);
Arrays.sort(sequence);
TreeNode root = null;
try{
root = reConstrcut(sequence,post,
0,sequence.length-1,0,post.length-1);
}catch (Exception e){ //构造过程中，发生异常，即构造失败
return false;
}
//root==null 也是构造失败
return root!=null;
}
private TreeNode reConstrcut(int[] in,int[] post,
int inStart,int inEnd,int postStart,int postEnd){
if(inStart>inEnd || postStart>postEnd){
return null;
}
TreeNode root = new TreeNode(post[postEnd]);
int index=-1;
for(int i=inStart;i<=inEnd;i++){
if(in[i]==post[postEnd]){
index=i;
break;
}
}
root.left = reConstrcut(in,post,inStart,index-1,
postStart,postStart+(index-inStart-1));
root.right=reConstrcut(in,post,index+1,inEnd,
postStart+(index-inStart),postEnd-1);
return root;
}//思路二：
//利用二分搜索树性质
//将 sequence 划分为左右子树序列
//如果能构成二分搜索树
//左子树中的数值 <= 根节点值
//右子树中的数值 > 根节点值
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null || sequence.length==0){
return false;
}
return verify(sequence,0,sequence.length-1);
}
private boolean verify(int[] squence,int first,int last){
if(last-first<=1){
//当 last-first==0 时，只有 1 个结点，显然正确
//当 last-first==1 时，只有 2 个结点，此时不管是顺序的还是逆序的都可以构造
return true;
}
int rootVal = squence[last]; //后序遍历最后一个元素值就是根节点的值
int cutIndex = first; // cutIndex 用于切分左右子树
while (cutIndex<last && squence[cutIndex]<=rootVal){ //二分搜索树中左子树所有结点值都小于根节点值
cutIndex++;
}
//左子树 [first,curIndex-1]
//cutIndex 就是右子树的后序遍历的首元素的下标
for(int i=cutIndex;i<last;i++){ //右子树[curIndex,last-1]
if(rootVal>squence[i]){ //右子树中存在大于根节点的值，返回 false
return false;
}
}
return verify(squence,first,cutIndex-1) &&
verify(squence,cutIndex,last-1);
}二叉搜索树与双向链表
//思路：
//二分搜索树有序：中序遍历
//难点在于不能创建任何新节点
private TreeNode pre = null; //指向当前节点的前一个节点
private TreeNode head = null; //指向头节点
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
inOrder(pRootOfTree);
return head;
}
// node 是当前节点
private void inOrder(TreeNode node){
if(node==null){
return;
}
inOrder(node.left);
node.left = pre;
if(pre!=null){ //说明 root 不是头结点
pre.right=node;
}
pre=node;
if(head==null){
head = node;
}
inOrder(node.right);
}
