트리의 기본 동작 코드
package com.lifeibigdata.algorithms.tree;
/**
* Created by lifei on 16/5/26.
*/
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
* http://blog.csdn.net/luckyxiaoqiang/article/details/7518888
* http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html (3)
*
* TODO: !
*
* 1. : getNodeNumRec( ),getNodeNum( )
* 2. : getDepthRec( ),getDepth
* 3. , , : preorderTraversalRec, preorderTraversal, inorderTraversalRec, postorderTraversalRec
* (https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2)
* 4. ( , ): levelTraversal, levelTraversalRec( !)
* 5. : convertBST2DLLRec, convertBST2DLL
* 6. K :getNodeNumKthLevelRec, getNodeNumKthLevel
* 7. :getNodeNumLeafRec, getNodeNumLeaf
* 8. :isSameRec, isSame
* 9. :isAVLRec
* 10. ( ):mirrorRec, mirrorCopyRec
* 10.1 :isMirrorRec
* 11. :getLastCommonParent, getLastCommonParentRec, getLastCommonParentRec2
* 12. :getMaxDistanceRec
* 13. :rebuildBinaryTreeRec
* 14. :isCompleteBinaryTree, isCompleteBinaryTreeRec
*
*/
public class BinaryTreeSummary {
/*
1
/ \
2 3
/ \ \
4 5 6
*/
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
/**
* : O(n)
* (1) , 0
* (2) , = + + 1
*/
public static int getNodeNumRec(TreeNode root) {
if (root == null) {
return 0;
} else {
return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1; // 1
}
}
/**
* O(n): LevelOrderTraversal,
* Queue, Java LinkedList
*/
public static int getNodeNum(TreeNode root) {
if(root == null){
return 0;
}
int count = 1; // 1
Queue queue = new LinkedList();
queue.add(root); //
while(!queue.isEmpty()){
TreeNode cur = queue.remove(); //
if(cur.left != null){ // ,
queue.add(cur.left);
count++;
}
if(cur.right != null){ // ,
queue.add(cur.right);
count++;
}
}
return count;
}
/**
* ( ) : O(n)
* (1) , 0
* (2) , = max( , ) + 1
*/
public static int getDepthRec(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepthRec(root.left);
int rightDepth = getDepthRec(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
/**
* ( ) : O(n)
* LevelOrderTraversal, Queue
*/
public static int getDepth(TreeNode root) {
if(root == null){
return 0;
}
int depth = 0; //
int currentLevelNodes = 1; // Level,node
int nextLevelNodes = 0; // Level,node
LinkedList queue = new LinkedList();
queue.add(root);
while( !queue.isEmpty() ){
TreeNode cur = queue.remove(); //
currentLevelNodes--; // Level node
if(cur.left != null){ // ,
queue.add(cur.left);
nextLevelNodes++; // Level node
}
if(cur.right != null){ // ,
queue.add(cur.right);
nextLevelNodes++;
}
if(currentLevelNodes == 0){ // *********** ,
depth++; // ******
currentLevelNodes = nextLevelNodes; //
nextLevelNodes = 0;
}
}
return depth;
}
/**
*
* @param root
* @return
*/
public static int getWidth(TreeNode root) {
if(root == null){
return 0;
}
int maxWidth = 1;
LinkedList queue = new LinkedList();
queue.add(root);
while (true){
int len = queue.size();
if (len == 0)
break;
while (len > 0){
TreeNode t = queue.removeFirst();
len--;
if (t.left != null){
queue.add(t.left);
}
if (t.right != null){
queue.add(t.right);
}
}
maxWidth = Math.max(maxWidth,queue.size());
}
return maxWidth;
}
/**
* , , :
* (1) ,
* (2) , , ,
*/
public static void preorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preorderTraversalRec(root.left);
preorderTraversalRec(root.right);
}
/**
* : stack,
* http://www.youtube.com/watch?v=uPTCbdHSFg4
*/
public static void preorderTraversal(TreeNode root) {
if(root == null){
return;
}
Stack stack = new Stack(); // stack
stack.push(root);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop(); //
System.out.print(cur.val + " ");
// : , ,
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
/**
*
* (1) , 。
* (2) , , ,
*/
public static void inorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
inorderTraversalRec(root.left);
System.out.print(root.val + " ");
inorderTraversalRec(root.right);
}
/**
* , ,
* ,
* http://www.youtube.com/watch?v=50v1sJkjxoc
*
* , ,
* http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
*/
public static void inorderTraversal(TreeNode root){ // , , , , ,
if(root == null){
return;
}
Stack stack = new Stack();
TreeNode cur = root;
while( true ){
while(cur != null){ //
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()){
break;
}
// , //left root
cur = stack.pop(); //root
System.out.print(cur.val + " ");
cur = cur.right; //
}
}
/**
*
* (1) ,
* (2) , , ,
*/
public static void postorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
postorderTraversalRec(root.left);
postorderTraversalRec(root.right);
System.out.print(root.val + " ");
}
/**
*
* http://www.youtube.com/watch?v=hv-mJUs5mvU
*
*/
public static void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack s = new Stack(); // stack node
Stack output = new Stack();// stack stack
s.push(root);
while( !s.isEmpty() ){ // stack
TreeNode cur = s.pop(); // stack
output.push(cur);
// : , ,
//
if(cur.left != null){ // stack
s.push(cur.left);
}
if(cur.right != null){
s.push(cur.right);
}
}
while( !output.isEmpty() ){ // stack,
System.out.print(output.pop().val + " ");
}
}
/**
* ( , )
* , 。 , 。 , :
* , , ,
*/
public static void levelTraversal(TreeNode root) {
if (root == null) {
return;
}
LinkedList queue = new LinkedList();
queue.push(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.removeFirst();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
/**
* ( )
* level traversal
* ArrayList, ArrayList。
* ArrayList size level
*
* !
* http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal#answer-container-2543
*/
public static void levelTraversalRec(TreeNode root) {
ArrayList> ret = new ArrayList>();
dfs(root, 0, ret);
System.out.println(ret);
}
private static void dfs(TreeNode root, int level, ArrayList> ret){
if(root == null){
return;
}
// ArrayList
if(level >= ret.size()){
ret.add(new ArrayList());
}
ret.get(level).add(root.val); // ArrayList
dfs(root.left, level+1, ret); //
dfs(root.right, level+1, ret);
}
/**
* , 。
* :
* http://stackoverflow.com/questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016
* , ,root ,
* root
*/
public static TreeNode convertBST2DLLRec(TreeNode root) {
root = convertBST2DLLSubRec(root);
// root , root
while(root.left != null){
root = root.left;
}
return root;
}
/**
* BST (DLL)
*/
public static TreeNode convertBST2DLLSubRec(TreeNode root){
if(root==null || (root.left==null && root.right==null)){
return root;
}
TreeNode tmp = null;
if(root.left != null){ //
tmp = convertBST2DLLSubRec(root.left);
while(tmp.right != null){ //
tmp = tmp.right;
}
tmp.right = root; // root
root.left = tmp;
}
if(root.right != null){ //
tmp = convertBST2DLLSubRec(root.right);
while(tmp.left != null){ //
tmp = tmp.left;
}
tmp.left = root; // root
root.right = tmp;
}
return root;
}
/**
*
// * inorder traversal
*/
public static TreeNode convertBST2DLL(TreeNode root) {
if(root == null){
return null;
}
Stack stack = new Stack();
TreeNode cur = root; //
TreeNode old = null; //
TreeNode head = null; //
while( true ){
while(cur != null){ //
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()){
break;
}
// ,
cur = stack.pop();
if(old != null){
old.right = cur;
}
if(head == null){ // /
head = cur;
}
old = cur; // old
cur = cur.right; //
}
return head;
}
/**
* K :
* (1) k<1 0
* (2) k==1, 1
* (3) k>1, root k-1 root k-1
*
* root k root k-1 ( root )
* root k-1 ( root )
*
* , ,
*
*/
public static int getNodeNumKthLevelRec(TreeNode root, int k) {
if (root == null || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
int numLeft = getNodeNumKthLevelRec(root.left, k - 1); // root k-1
int numRight = getNodeNumKthLevelRec(root.right, k - 1); // root k-1
return numLeft + numRight;
}
/**
* K :
* getDepth
*/
public static int getNodeNumKthLevel(TreeNode root, int k){
if(root == null){
return 0;
}
Queue queue = new LinkedList();
queue.add(root);
int i = 1;
int currentLevelNodes = 1; // Level,node
int nextLevelNodes = 0; // Level,node
while( !queue.isEmpty() && i queue = new LinkedList();
queue.add(root);
int leafNodes = 0; // Level,node
while( !queue.isEmpty() ){
TreeNode cur = queue.remove(); //
if(cur.left != null){ // ,
queue.add(cur.left);
}
if(cur.right != null){ // ,
queue.add(cur.right);
}
if(cur.left==null && cur.right==null){ //
leafNodes++;
}
}
return leafNodes;
}
/**
* 。
* :
* (1) ,
* (2) , ,
* (3) , ,
*/
public static boolean isSameRec(TreeNode r1, TreeNode r2) {
// ,
if (r1 == null && r2 == null) {
return true;
}
// , ,
else if (r1 == null || r2 == null) {
return false;
}
if(r1.val != r2.val){
return false;
}
boolean leftRes = isSameRec(r1.left, r2.left); //
boolean rightRes = isSameRec(r1.right, r2.right); //
return leftRes && rightRes;
}
/**
* ( )
* , preorder
*/
public static boolean isSame(TreeNode r1, TreeNode r2) {
// , true
if(r1==null && r2==null){
return true;
}
// , , false
if(r1==null || r2==null){
return false;
}
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(r1);
s2.push(r2);
while(!s1.isEmpty() && !s2.isEmpty()){
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if(n1==null && n2==null){
continue;
}else if(n1!=null && n2!=null && n1.val==n2.val){
s1.push(n1.right);
s1.push(n1.left);
s2.push(n2.right);
s2.push(n2.left);
}else{
return false;
}
}
return true;
}
/**
* :
* (1) ,
* (2) , AVL 1, ,
*/
public static boolean isAVLRec(TreeNode root) {
if(root == null){ // ,
return true;
}
// 1, , getDepthRec()
if(Math.abs(getDepthRec(root.left) - getDepthRec(root.right)) > 1){
return false;
}
//
return isAVLRec(root.left) && isAVLRec(root.right);
}
/**
* :
* (1) ,
* (2) , ,
*/
// 1. ,
public static TreeNode mirrorRec(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorRec(root.left);
TreeNode right = mirrorRec(root.right);
root.left = right;
root.right = left;
return root;
}
// 2. ,
public static TreeNode mirrorCopyRec(TreeNode root){
if(root == null){
return null;
}
TreeNode newNode = new TreeNode(root.val);
newNode.left = mirrorCopyRec(root.right);
newNode.right = mirrorCopyRec(root.left);
return newNode;
}
// 3.
public static boolean isMirrorRec(TreeNode r1, TreeNode r2){
// , true
if(r1==null && r2==null){
return true;
}
// , , false
if(r1==null || r2==null){
return false;
}
// ,
if(r1.val != r2.val){
return false;
}
// r1 r2
// r1 r2
return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);
}
// 1. ,
public static void mirror(TreeNode root) {
if(root == null){
return;
}
Stack stack = new Stack();
stack.push(root);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop();
//
TreeNode tmp = cur.right;
cur.right = cur.left;
cur.left = tmp;
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
// 2. ,
public static TreeNode mirrorCopy(TreeNode root){
if(root == null){
return null;
}
Stack stack = new Stack();
Stack newStack = new Stack();
stack.push(root);
TreeNode newRoot = new TreeNode(root.val);
newStack.push(newRoot);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop();
TreeNode newCur = newStack.pop();
if(cur.right != null){
stack.push(cur.right);
newCur.left = new TreeNode(cur.right.val);
newStack.push(newCur.left);
}
if(cur.left != null){
stack.push(cur.left);
newCur.right = new TreeNode(cur.left.val);
newStack.push(newCur.right);
}
}
return newRoot;
}
/**
*
* :
* (1) ,
* (2) , ; ,
*/
public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) {
if (findNodeRec(root.left, n1)) { // n1
if (findNodeRec(root.right, n2)) { // n2
return root; //
} else { // n2
return getLastCommonParentRec(root.left, n1, n2); //
}
} else { // n1
if (findNodeRec(root.left, n2)) { // n2
return root;
} else { // n2
return getLastCommonParentRec(root.right, n1, n2); //
}
}
}
// ,
private static boolean findNodeRec(TreeNode root, TreeNode node) {
if (root == null || node == null) {
return false;
}
if (root == node) {
return true;
}
//
boolean found = findNodeRec(root.left, node);
if (!found) { // ,
found = findNodeRec(root.right, node);
}
return found;
}
// ( )
public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) {
if(root == null){
return null;
}
// match, node
if(root.equals(n1) || root.equals(n2)){
return root;
}
TreeNode commonInLeft = getLastCommonParentRec2(root.left, n1, n2);
TreeNode commonInRight = getLastCommonParentRec2(root.right, n1, n2);
// , , root
if(commonInLeft!=null && commonInRight!=null){
return root;
}
//
if(commonInLeft != null){
return commonInLeft;
}
return commonInRight;
}
/**
* :
* , ,
*/
public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {
if (root == null || n1 == null || n2 == null) {
return null;
}
ArrayList p1 = new ArrayList();
boolean res1 = getNodePath(root, n1, p1);
ArrayList p2 = new ArrayList();
boolean res2 = getNodePath(root, n2, p2);
if (!res1 || !res2) {
return null;
}
TreeNode last = null;
Iterator iter1 = p1.iterator();
Iterator iter2 = p2.iterator();
while (iter1.hasNext() && iter2.hasNext()) {
TreeNode tmp1 = iter1.next();
TreeNode tmp2 = iter2.next();
if (tmp1 == tmp2) {
last = tmp1;
} else { //
break;
}
}
return last;
}
// node path
private static boolean getNodePath(TreeNode root, TreeNode node, ArrayList path) {
if (root == null) {
return false;
}
path.add(root); //
if (root == node) {
return true;
}
boolean found = false;
found = getNodePath(root.left, node, path); //
if (!found) { // ,
found = getNodePath(root.right, node, path);
}
if (!found) { // , , !
path.remove(root);
}
return found;
}
/**
* 。 (distance / diameter)
* :
* (1) , 0, , 0
* (2) , , ,
* + ,
* 。
*
* http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
*
* :
A: , , 。
B: , , 。
, ,
*/
public static Result getMaxDistanceRec(TreeNode root){
if(root == null){
Result empty = new Result(0, -1); // +1 , (NULL) 0
return empty;
}
//
Result lmd = getMaxDistanceRec(root.left);
Result rmd = getMaxDistanceRec(root.right);
Result res = new Result();
res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1; //
// A B
res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) );
return res;
}
private static class Result{
int maxDistance;
int maxDepth;
public Result() {
}
public Result(int maxDistance, int maxDepth) {
this.maxDistance = maxDistance;
this.maxDepth = maxDepth;
}
}
/**
* 13. ( )
* :
* http://crackinterviewtoday.wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals/
* ,
*/
public static TreeNode rebuildBinaryTreeRec(List preOrder, List inOrder){
TreeNode root = null;
List leftPreOrder;
List rightPreOrder;
List leftInorder;
List rightInorder;
int inorderPos;
int preorderPos;
if ((preOrder.size() != 0) && (inOrder.size() != 0))
{
// preorder root
root = new TreeNode(preOrder.get(0));
// Based upon the current node data seperate the traversals into leftPreorder, rightPreorder,
// leftInorder, rightInorder lists
// root , root , preorder,inorder root
inorderPos = inOrder.indexOf(preOrder.get(0)); // inorder
leftInorder = inOrder.subList(0, inorderPos);
rightInorder = inOrder.subList(inorderPos + 1, inOrder.size());
preorderPos = leftInorder.size(); // preorder
leftPreOrder = preOrder.subList(1, preorderPos + 1);
rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size());
root.left = rebuildBinaryTreeRec(leftPreOrder, leftInorder); // root preorder inorder
root.right = rebuildBinaryTreeRec(rightPreOrder, rightInorder); // root preorder inorder
}
return root;
}
/**
14. ( )
h, h , (1~h-1) ,
h , 。
, ( , ) , ,
, , 。
*/
public static boolean isCompleteBinaryTree(TreeNode root){
if(root == null){
return false;
}
Queue queue = new LinkedList();
queue.add(root);
boolean mustHaveNoChild = false;
boolean result = true;
while( !queue.isEmpty() ){
TreeNode cur = queue.remove();
if(mustHaveNoChild){ // , ( )
if(cur.left!=null || cur.right!=null){
result = false;
break;
}
} else {
if(cur.left!=null && cur.right!=null){ // ,
queue.add(cur.left);
queue.add(cur.right);
}else if(cur.left!=null && cur.right==null){ // , ,
mustHaveNoChild = true;
queue.add(cur.left);
}else if(cur.left==null && cur.right!=null){ // , !
result = false;
break;
}else{ // ,
mustHaveNoChild = true;
}
}
}
return result;
}
/**
* 14. ( )
* http://stackoverflow.com/questions/1442674/how-to-determine-whether-a-binary-tree-is-complete
*
*/
public static boolean isCompleteBinaryTreeRec(TreeNode root){
// Pair notComplete = new Pair(-1, false);
// return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete);
return isCompleteBinaryTreeSubRec(root).height != -1;
}
// ( )
public static boolean isPerfectBinaryTreeRec(TreeNode root){
return isCompleteBinaryTreeSubRec(root).isFull;
}
// , Pair class
public static Pair isCompleteBinaryTreeSubRec(TreeNode root){
if(root == null){
return new Pair(0, true);
}
Pair left = isCompleteBinaryTreeSubRec(root.left);
Pair right = isCompleteBinaryTreeSubRec(root.right);
// , , ( )
if(left.isFull && left.height==right.height){
return new Pair(1+left.height, right.isFull);
}
// , ,
// , -1,
// !
if(right.isFull && left.height==right.height+1){
return new Pair(1+left.height, false);
}
// , -1
return new Pair(-1, false);
}
private static class Pair{
int height; //
boolean isFull; //
public Pair(int height, boolean isFull) {
this.height = height;
this.isFull = isFull;
}
public boolean equalsTo(Pair obj){
return this.height==obj.height && this.isFull==obj.isFull;
}
}
public static void main(String[] args) {
TreeNode r1 = new TreeNode(1);
TreeNode r2 = new TreeNode(2);
TreeNode r3 = new TreeNode(3);
TreeNode r4 = new TreeNode(4);
TreeNode r5 = new TreeNode(5);
TreeNode r6 = new TreeNode(6);
r1.left = r2;
r1.right = r3;
r2.left = r4;
r2.right = r5;
r3.right = r6;
//
System.out.println(getNodeNumRec(r1));
System.out.println(getNodeNum(r1));
// System.out.println(getDepthRec(r1));
// System.out.println(getDepth(r1));
// System.out.println(getWidth(r1));
//
// preorderTraversalRec(r1); //1 2 4 5 3 6
// System.out.println();
// preorderTraversal(r1);
// System.out.println();
// inorderTraversalRec(r1); //4 2 5 1 3 6
// System.out.println();
// inorderTraversal(r1);
// System.out.println();
// postorderTraversalRec(r1); //4 5 2 6 3 1
// System.out.println();
// postorderTraversal(r1);
// System.out.println();
//
// levelTraversal(r1);
// System.out.println();
// levelTraversalRec(r1);
// System.out.println();
// TreeNode tmp = convertBSTRec(r1);
// while(true){
// if(tmp == null){
// break;
// }
// System.out.print(tmp.val + " ");
// if(tmp.right == null){
// break;
// }
// tmp = tmp.right;
// }
// System.out.println();
// while(true){
// if(tmp == null){
// break;
// }
// System.out.print(tmp.val + " ");
// if(tmp.left == null){
// break;
// }
// tmp = tmp.left;
// }
// TreeNode tmp = convertBST2DLL(r1);
// while(true){
// if(tmp == null){
// break;
// }
// System.out.print(tmp.val + " ");
// if(tmp.right == null){
// break;
// }
// tmp = tmp.right;
// }
// System.out.println(getNodeNumKthLevelRec(r1, 2));
// System.out.println(getNodeNumKthLevel(r1, 2));
// System.out.println(getNodeNumLeafRec(r1));
// System.out.println(getNodeNumLeaf(r1));
// System.out.println(isSame(r1, r1));
// inorderTraversal(r1);
// System.out.println();
// mirror(r1);
// TreeNode mirrorRoot = mirrorCopy(r1);
// inorderTraversal(mirrorRoot);
// System.out.println(isCompleteBinaryTree(r1));
// System.out.println(isCompleteBinaryTreeRec(r1));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.