데이터 구조의 이 진 트 리 전체 편 (자바)

머리말

면접 에서 나 무 는 모두 이 진 트 리, 즉 좌우 두 노드 가 있 는 나무

이다.

명심: root. left 는 왼쪽 나무, root. right 는 오른쪽 나무, 나무의 재 귀 를 통 해 문 제 를 해결 합 니 다

.
이 진 트 리 정의

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    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;  
        }  
    } 

비 귀속: 교체

 /** *               O(n)： *      LevelOrderTraversal， *     Queue， Java     LinkedList    */  
    public static int getNodeNum(TreeNode root) {  
        if(root == null){  
            return 0;  
        }  
        int count = 1;  
        Queue<TreeNode> queue = new LinkedList<TreeNode>();  
        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<TreeNode> queue = new LinkedList<TreeNode>();  
        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;  
    } 

앞 순 서 를 편력 하 다.
먼저 뿌리 를 옮 겨 다 니 기
귀착 하 다

public static void preorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        System.out.print(root.val + " ");  
        preorderTraversalRec(root.left);  
        preorderTraversalRec(root.right);  
    }  

비 귀속: 귀속 - > 비 귀속 이용 창고

   
       
While    
          
         
    If      ，       
    IF      ，       

코드 구현:

/** *         ：     stack，          * */  
    public static void preorderTraversal(TreeNode root) {  
        if(root == null){  
            return;  
        }  

        Stack<TreeNode> stack = new Stack<TreeNode>();      //   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.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ */  
    public static void inorderTraversal(TreeNode root){  
        if(root == null){  
            return;  
        }  
        Stack<TreeNode> stack = new Stack<TreeNode>();  
        TreeNode cur = root;  

        while( true ){  
            while(cur != null){     //                   
                stack.push(cur);  
                cur = cur.left;  
            }  

            if(stack.isEmpty()){  
                break;  
            }  

            //             ，         
            cur = stack.pop();  
            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 + " ");  
    }  

비 귀속

두 개의 스 택 stk, stk 2 를 설치 합 니 다.

뿌리 결산 점 을 첫 번 째 스 택 stk 에 누 르 기;

stk 스 택 꼭대기 의 결산 점 을 팝 업 하고 이 결산 점 을 두 번 째 스 택 stk 2 에 누 릅 니 다.

현재 결산 점 의 왼쪽 아이 와 오른쪽 아 이 를 각각 스 택 stk 에 넣는다.

모든 요소 가 stk 2 에 눌 린 후에 stk 2 의 스 택 끝 점 을 차례대로 팝 업 하고 방문 합 니 다.

첫 번 째 창고 에 들 어 가 는 순 서 는 뿌리 결산 점, 왼쪽 아이 와 오른쪽 아이 입 니 다.그래서 두 번 째 창고 에 들 어 가 는 순 서 는 뿌리 결산 점, 오른쪽 아이 와 왼쪽 아이 입 니 다.따라서 튀 어 나 오 는 순 서 는 왼쪽 아이, 오른쪽 아이, 뿌리 결점 이다.

/** *          * http://www.youtube.com/watch?v=hv-mJUs5mvU * */  
    public static void postorderTraversal(TreeNode root) {  
        if (root == null) {  
            return;  
        }  

        Stack<TreeNode> s = new Stack<TreeNode>();      //    stack    node        
        Stack<TreeNode> output = new Stack<TreeNode>();//    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 + " ");  
        }  
    }  

복잡 도 분석
이 진 트 리 가 옮 겨 다 니 는 비 재 귀적 실현 은 모든 노드 를 한 번 만 옮 겨 다 니 기 때문에 시간 복잡 도 는 O (n) 이다.스 택 을 사 용 했 는데 공간 복잡 도 는 이 진 트 리 의 높이 이기 때문에 공간 복잡 도 는 O (n) 이다.
층 차 를 편력 하 다
비 귀속:

 /** *        （       ，    ）   *          ，      。     ，        。      ，      ：       * ，  ，             ，       */  
    public static void levelTraversal(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();  
        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<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();  
        dfs(root, 0, ret);  
        System.out.println(ret);  
    }  

    private static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret){  
        if(root == null){  
            return;  
        }  

        //       ArrayList       
        if(level >= ret.size()){  
            ret.add(new ArrayList<Integer>());  
        }  

        ret.get(level).add(root.val);   //             ArrayList  
        dfs(root.left, level+1, ret);       //                 
        dfs(root.right, level+1, ret);  
    }  

이 진 트 리 는 질서 있 는 양 방향 링크 로 바 뀌 었 다.
이 진 트 리 를 입력 하고 이 진 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 트 리 의 노드 포인터 의 방향 만 조정 할 수 있 습 니 다.https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
귀속:

public class Solution {
    TreeNode phead;  //  
    TreeNode realhead;  //   
    public TreeNode Convert(TreeNode pRootOfTree) {

        if(pRootOfTree==null)
            return pRootOfTree;

        ConvertSub(pRootOfTree);

        return realhead;
    }

    //    
    public void ConvertSub(TreeNode root){
        if(root==null)
            return ;
        ConvertSub(root.left);
        if(phead==null){
            phead=root;
            realhead=root;
        }
        else{
            phead.right=root;
            root.left=phead;
            phead=root;
        }
        ConvertSub(root.right);
    }


}

비 귀속: 교체

/** *                      // *   inorder traversal    */  
    public static TreeNode convertBST2DLL(TreeNode root) {  
        if(root == null){  
            return null;  
        }  
        Stack<TreeNode> stack = new Stack<TreeNode>();  
        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 층 의 노드 갯 수 구하 기 *
귀착 하 다

 /** *      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<TreeNode> queue = new LinkedList<TreeNode>();  
        queue.add(root);  

        int i = 1;  
        int currentLevelNodes = 1;      //   Level，node    
        int nextLevelNodes = 0;         //    Level，node    

        while( !queue.isEmpty() && i<k){  
            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){ //                 
                currentLevelNodes = nextLevelNodes;     //           
                nextLevelNodes = 0;  
                i++;            //        
            }  
        }  

        return currentLevelNodes;  
    }  

이 진 트 리 의 잎 결점 의 개 수 를 구하 다.
귀속:

 /** *             （  ） */  
    public static int getNodeNumLeafRec(TreeNode root) {  
        //  root   ，    
        if (root == null) {  
            return 0;  
        }  

        //          1 
        if (root.left == null && root.right == null) {  
            return 1;  
        }  

        //                ，       
        return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);  
    }  

비 귀속:

/** *             （  ） *     Level order traversal */  
    public static int getNodeNumLeaf(TreeNode root) {  
        if(root == null){  
            return 0;  
        }  
        Queue<TreeNode> queue = new LinkedList<TreeNode>();  
        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<TreeNode> s1 = new Stack<TreeNode>();  
        Stack<TreeNode> s2 = new Stack<TreeNode>();  

        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<TreeNode> stack = new Stack<TreeNode>();  
        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<TreeNode> stack = new Stack<TreeNode>();  
        Stack<TreeNode> newStack = new Stack<TreeNode>();  
        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;  
    }  

이 진 트 리 중 노드 의 최대 거 리 를 구하 십시오.

 /** *                                 。 (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;  
        }  
    }  

이 진 트 리 가 완전 이 진 트 리 인지 아 닌 지 판단 하기
비 재 귀적 교체

 /** 14.              （  ）          h，   h   ，     (1～h-1)            ，   h                ，        。      ，   （    ，    ）     ，              ，            ，                 ，         。 */  
    public static boolean isCompleteBinaryTree(TreeNode root){  
        if(root == null){  
            return false;  
        }  

        Queue<TreeNode> queue = new LinkedList<TreeNode>();  
        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;  
        }  
    }  

이 진 트 리 덤 프
문제: 무질서 한 이 진 트 리 에 저 장 된 정수 집합 을 지정 합 니 다.배열 정렬 알고리즘 을 사용 하여 이 나 무 를 하나의 더미 로 바 꾸 고 이 더 미 는 균형 이 잡 힌 이 진 트 리 를 바 텀 데이터 구조 로 사용 합 니 다.
참고