摘要：實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu)棧，隊(duì)列，鏈表這篇筆記側(cè)重點(diǎn)二叉樹的三種遍歷前中后迭代非迭代代碼重建二叉樹的代碼與分析和關(guān)于二叉樹的題簡(jiǎn)單理解二叉查找樹紅黑樹，的性質(zhì)，實(shí)際用途。同時(shí)，以對(duì)應(yīng)的節(jié)點(diǎn)為邊界，就會(huì)把中序遍歷的結(jié)果分為左子樹和右子樹。

雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復(fù)制黨

以下是算法導(dǎo)論第十章的學(xué)習(xí)筆記 即 劍指offer題目
劍指offer電子書 見(jiàn)我的github https://github.com/GsmToday/JianZhi-offer/tree/master

前面總結(jié)了，棧，隊(duì)列，鏈表。 Java 實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 1（棧，隊(duì)列，鏈表）
這篇筆記側(cè)重點(diǎn)：
1 二叉樹的三種遍歷（前中后）迭代非迭代代碼
2 重建二叉樹的代碼與分析 和 關(guān)于二叉樹的題 簡(jiǎn)單理解
3 二叉查找樹, 紅黑樹，Btree的性質(zhì)，實(shí)際用途。比如hashmap用到了紅黑樹

二叉樹最重要的操作某過(guò)于遍歷，namely 按照某一順序訪問(wèn)樹中的所有節(jié)點(diǎn)。
通常有四種遍歷方式：

深度優(yōu)先：

- 前序遍歷 （根-左-右）10,6,4,8,14,12,16
用途：1 拷貝樹。 2 計(jì)算前綴表達(dá)式
- 中序遍歷 （左-根-右）4,6,8,10,12,14,16
用途：BST（二叉搜索樹）的中序遍歷以非降序方式輸出節(jié)點(diǎn)。
- 后序遍歷 （右-左-根）4,8,8,12,16,14,10
后序遍歷的用途：1 刪除樹 2 計(jì)算后綴表達(dá)式
2. 廣度優(yōu)先：
- 層序遍歷

二叉樹的遍歷時(shí)間復(fù)雜度，無(wú)論遞歸與否，方式與否，都是O(n). 這是因?yàn)槊總€(gè)算法都要遍歷每個(gè)節(jié)點(diǎn)僅僅一次。

java    public static void preOrderTraverse(Treenode rootnode){
        Treenode p = rootnode;
        if(p!=null){
            System.out.println(p.value);
            preOrderTraverse(p.leftchild);
            preOrderTraverse(p.rightchild);
        }
        else return;
    }

java    public static void preOrderNonrecur(Treenode rootnode){
        if(rootnode==null){
            return;
        }
        Treenode p = rootnode;
        Stack stack = new Stack();
        stack.push(p);
        while(stack.isEmpty()!=true){
            p = stack.pop();
            System.out.println(p.value);
            if(p.rightchild != null ){
                stack.push(p.rightchild);
            }
            if(p.leftchild != null){
                stack.push(p.leftchild);
            }
        }
    }

java    public static void inOrderTraverse(Treenode rootnode){
        Treenode p = rootnode;
        if(p!=null){
            inOrderTraverse(p.leftchild);
            System.out.println(p.value);
            inOrderTraverse(p.rightchild);
        }
        else return;
    }

java    public static void inOrderNonrecur(Treenode rootnode){
        if(rootnode==null){
            return;
        }

        Treenode current = rootnode;
        Stack stack = new Stack();
        while(current != null||stack.isEmpty()!=true){
            while(current!=null){
                stack.push(current);
                current = current.leftchild;
            }
            if(current==null){
                Treenode node = stack.pop();
                System.out.println(node.value);
                current = node.rightchild;
                }
        }   
    }

java    public static void postOrderTraverse(Treenode rootnode){
        Treenode p = rootnode;
        if(p!=null){
            postOrderTraverse(p.leftchild);
            postOrderTraverse(p.rightchild);
            System.out.println(p.value);
        }
        else return;
    }

java    public static void postOrderNonrecur(Treenode rootnode){
        if(rootnode==null){
            return;
        }   
        Stack stack = new Stack();
        Treenode current = rootnode;
        while(current !=null || stack.isEmpty()!=true){     
            //step 1 
            while(current!=null){   
                if(current.rightchild!=null){
                    stack.push(current.rightchild);
                }
                stack.push(current);
                current = current.leftchild;
            }

            // step2 既然出棧了，該節(jié)點(diǎn)肯定沒(méi)有左孩子。
            current = stack.pop();
    　　　　if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek())  {
                    stack.pop(); //出棧右孩子
                    stack.push(current);
                    current = current.rightchild;
            }
            else{
                System.out.println(current.value);
                current = null;
            }
        }
    }

java    public static int height(Treenode rootnode){
        if(rootnode == null){
            return -1;
        }
        int lheight = height(rootnode.leftchild); 計(jì)算該節(jié)點(diǎn)左孩子的高度
        int rheight = height(rootnode.rightchild); 計(jì)算該節(jié)點(diǎn)右孩子的高度
        return Math.max(lheight, rheight)+1; 返回給該節(jié)點(diǎn)自己的高度
    }

javapublic class Solution {
       public List> levelOrder(TreeNode rootnode) {
        List> resultlist = new ArrayList>();

        for(int level = 0; level<= height(rootnode);level++)
        {
            List list = new ArrayList();
            printGivenLevel(rootnode,level,list);
            resultlist.add(list);
        }
        return resultlist;

    }
    public int height(TreeNode rootnode){
        if(rootnode==null){
            return -1;
        }
        else{
            return Math.max(height(rootnode.left),height(rootnode.right))+1;
        }
    }
    public void printGivenLevel(TreeNode rootnode, int level, List list){
        if(rootnode==null){
            return;
        }   
        if(level == 0){
            list.add(rootnode.val);
        }
        else{
            printGivenLevel(rootnode.left, level-1, list);
            printGivenLevel(rootnode.right, level-1, list);
        }
    }
}

java    public static void LevelOrderNonRecur(Treenode rootnode){
        Treenode tempnode = rootnode; 
        ArrayDeque queue=new ArrayDeque();

        if(rootnode==null){
            return;
        }   
        queue.add(tempnode);
        while(queue.isEmpty()!=true){
            tempnode = queue.remove();
            System.out.println(tempnode.value);
            if(tempnode.leftchild!=null)
                queue.add(tempnode.leftchild);
            if(tempnode.rightchild!=null)
                queue.add(tempnode.rightchild);
        }       
    }

java  private int getHeight(TreeNode root) {  
      if (root == null) return 0;  
      int depL = getHeight(root.left);  
      int depR = getHeight(root.right);  
      if (depL < 0 || depR < 0 || Math.abs(depL - depR) > 1) return -1;  返回給該節(jié)點(diǎn)自己的value
      else return Math.max(depL, depR) + 1;    返回給該節(jié)點(diǎn)自己的value
    }  
    public boolean isBalanced(TreeNode root) {  
      return (getHeight(root) >= 0);  
    }

java   //遍歷Tree1,查找與Tree2 root相同的節(jié)點(diǎn)
  boolean  HasSubtree(TreeNode root1, TreeNode root2){
        boolean result = false;
        if(root1 != null && root2 != null){
            if(root1.val == root2.val){
                //查找到與Tree2 root相同的節(jié)點(diǎn)，接著判斷二者是否具有相同結(jié)構(gòu)
                result = DoesTree1hasTree2(root1,root2);
            }
            if(result != true)
                result = HasSubtree(root1.left, root2);
            if(result != true)
                result = HasSubtree(root1.right, root2);    
        }
        return result;
    }

java   boolean  DoesTree1hasTree2(TreeNode root1, TreeNode root2){
        boolean lflag = false;
        boolean rflag = false;
        //Tree2結(jié)束
        if(root2==null){
            return true;
        }
        //Tree2有節(jié)點(diǎn)時(shí)候，Tree1還有，說(shuō)明肯定不是包含關(guān)系
        if(root1==null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }
        else{
            lflag = DoesTree1hasTree2(root1.left,root2.left);
            rflag = DoesTree1hasTree2(root1.right,root2.right);
            return lflag && rflag;
        }
    }

java     public static TreeNode buildTree(int[] preOrder,int start, int[] inOrder,
int end,int length){    
            // 邊界驗(yàn)證      
            if (preOrder == null || preOrder.length == 0 || inOrder == null    
                    || inOrder.length == 0 || length <= 0) {    
                return null;    
            }    

            //根據(jù) 前序遍歷的第一個(gè)元素建立樹根節(jié)點(diǎn)      
            int value = preOrder[start];    
            TreeNode root = new TreeNode();    
            root.val = value;    

            // 遞歸終止條件：子樹只有一個(gè)節(jié)點(diǎn)      
            if (length == 1)    
                return root;    

            // 根據(jù) 前序遍歷的第一個(gè)元素在中序遍歷中的位置分拆樹的左子樹和右子樹      
            int i = 0;    
            while (i < length) {    
                if (value == inOrder[end - i]) {    
                    break;    
                }    
                i++;    
            }    

            // 建立子樹的左子樹      
            root.left = buildTree(preOrder, start + 1, inOrder,
             end - i - 1, length - 1 - i);    
            // 建立子樹的右子樹      
            root.right = buildTree(preOrder, start + length - i,
             inOrder, end, i);    

            return root;    
       }

java    public static TreeNode buildTree(int postOrder[], int pend, int inOrder[],int iend, int length){
        //boundary test
        if(postOrder == null || postOrder.length == 0 || inOrder == null || inOrder.length == 0 || postOrder.length != inOrder.length)
        {
            System.out.print("te");  
            return null;
        }
        //create root;
        TreeNode root = new TreeNode();
        int value = postOrder[pend];
        root.val = value;

        if(length ==1)
            return root;
        // search the index of the root in inorder
        int i =0;
        while(inOrder[iend-i]!=value){
            i++;
        }

        root.right =  buildTree(postOrder, pend-1, inOrder, iend,  i);  
        root.left =  buildTree(postOrder,  pend-i-1, inOrder, iend-i-1,  length-i-1);
        return root;

    }

java    private static Stack stack=new Stack();

    public static void findPathk(TreeNode root,int k,int sum){
        boolean isLeaf = false;
        // 為了追溯路徑，需要記住棧記錄父節(jié)點(diǎn)
        stack.push(root);
        // 記錄路徑的sum
        sum = root.val + sum;
        // 判斷是否路徑到頭
        if(root.left == null && root.right==null){
            isLeaf = true;
        }
        // 路徑到頭且和達(dá)到k
        if(isLeaf && sum ==k){
            System.out.println(stack);
        }
        // 左子樹
        if(root.left != null){
            findPathk(root.left,k,sum);
        }
        // 右子樹
        if(root.right != null){
            findPathk(root.right,k,sum);
        }
        // 出棧
        stack.pop();
    }