트리의 기본 동작 코드

33466 단어
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));

    }

}


좋은 웹페이지 즐겨찾기