等待那一束光

今日雞湯：

大腦的一切疲勞和壓力來(lái)自于過(guò)去和未來(lái)：對(duì)已經(jīng)發(fā)生的事情心有不甘，對(duì)將要發(fā)生的事情充滿不安。

愿你內(nèi)心平和肯污，踏踏實(shí)實(shí)活在當(dāng)下，不去悔恨過(guò)去吨枉，不去憂心未來(lái)仇箱。

今天一起來(lái)看樹啦，多刷題东羹，多刷題，有助于預(yù)防老年癡呆忠烛。

樹的基礎(chǔ)

1. 樹的最大深度

最大深度一定是到葉子節(jié)點(diǎn)了才能判斷是不是最深属提，為了記錄層數(shù)，可以在遍歷樹的時(shí)候定義新的數(shù)據(jù)結(jié)構(gòu)美尸，另外存下來(lái)當(dāng)前節(jié)點(diǎn)的層信息冤议，這樣訪問(wèn)葉子節(jié)點(diǎn)時(shí)，只要取出來(lái)判斷一下就可以了师坎。

    class NodeLevel{
        TreeNode node;
        int level;
         
        NodeLevel(TreeNode node,int level){
            this.node = node;
            this.level = level;
        }
    };
    /**
     *
     * @param root TreeNode類
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root == null)    return 0;
        return maxTreeDepth(root);
    }
     
    public int maxTreeDepth(TreeNode root){
        int maxDepthVal = 0;
        Stack<NodeLevel> parentStack = new Stack<NodeLevel>();
        Stack<NodeLevel> childrenStack = new Stack<NodeLevel>();
         
        // Add root to childrend stack
        childrenStack.push(new NodeLevel(root, 1));
        while(childrenStack.size() > 0){
            // Get current top node.
            NodeLevel topNode = childrenStack.pop();
            int currentLevel = topNode.level;
            if(topNode.node.right == null && topNode.node.left == null){
                if(currentLevel > maxDepthVal)    maxDepthVal = currentLevel;
            } else{
                // Add child nodes.
                if(topNode.node.left != null){
                    childrenStack.add(new NodeLevel(topNode.node.left, currentLevel + 1));
                } 
                if(topNode.node.right != null){
                    childrenStack.add(new NodeLevel(topNode.node.right, currentLevel + 1));
                }
            }
            parentStack.push(topNode);
        }
        return maxDepthVal;
    }

樹的遍歷

先來(lái)看樹的遍歷恕酸。主要分為前序（先序）、中序和后序胯陋，遍歷方法也很直接蕊温，遞歸和非遞歸袱箱，遞歸比較簡(jiǎn)單，主要看一下非遞歸方式义矛，涉及到不同的數(shù)據(jù)結(jié)構(gòu)发笔。

1. 前序遍歷

前序遍歷是按照<根、左凉翻、右>的方式來(lái)遍歷了讨，特點(diǎn)是根先出，所以可以用一個(gè)棧+一個(gè)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)制轰。棧用來(lái)存當(dāng)前節(jié)點(diǎn)前计，隊(duì)列用來(lái)按順序存放遍歷結(jié)果。注意壓棧是要先右再左垃杖，這樣出棧時(shí)才是先左后右男杈。

public ArrayList<Integer> preorderTraversal (TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> preOrderList = new ArrayList<Integer>();
        
        if(root == null)    return preOrderList;
        // Add root to stack
        stack.push(root);
        
        while(stack.size() != 0){
            // Get top node and put it into list.
            TreeNode topNode = stack.pop();
            preOrderList.add(topNode.val);
            
            // Push right node and left node to stack.
            if(topNode.right != null){
                stack.push(topNode.right);
            }
            if(topNode.left != null){
                stack.push(topNode.left);
            }
        }
        return preOrderList;
    }

2. 中序遍歷

中序遍歷是按照<左、中缩滨、右>的方式遍歷势就，特點(diǎn)是根在中間，可以根據(jù)根節(jié)點(diǎn)位置直接區(qū)分左右子樹的元素脉漏。因此苞冯，可以用一個(gè)棧，直接DFS侧巨，一直找左節(jié)點(diǎn)舅锄，為空時(shí)出棧，再加入右節(jié)點(diǎn)司忱。

public ArrayList<Integer> inorderTraversal (TreeNode root) {
        ArrayList<Integer> traversalList = new ArrayList<Integer>();
         
        Stack<TreeNode> stack = new Stack<TreeNode>();
         
        TreeNode currentNode = root;
        // When all nodes are processed,  stack will be empty, stop the loop.
        while(currentNode != null || !stack.isEmpty()){
            if(currentNode != null){
                // Push left node to the stack
                stack.push(currentNode);
                currentNode = currentNode.left;
            } else{
                // Pop current node in the stack
                TreeNode popedNode = stack.pop();
                // Add value to list
                traversalList.add(popedNode.val);
                // Push right node
                currentNode = popedNode.right;
            }
        }
        return traversalList;
    }

3. 后序遍歷

后序遍歷是按照<左皇忿、右、中>的方式遍歷坦仍，特點(diǎn)是根節(jié)點(diǎn)在最后鳍烁，因此用兩個(gè)棧，一個(gè)存放當(dāng)前節(jié)點(diǎn)繁扎，一個(gè)存放當(dāng)前節(jié)點(diǎn)的左右孩子幔荒。注意壓棧時(shí)先左后右。

public ArrayList<Integer> postorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> postorderList = new ArrayList<Integer>();
        if(root == null)    return postorderList;
         
        Stack<TreeNode> parentStack = new Stack<TreeNode>();
        Stack<TreeNode> childrenStack = new Stack<TreeNode>();
         
        // Put root into children stack.
        childrenStack.push(root);
         
        while(childrenStack.size() != 0){
            // Pop top node and push it into parent stack.
            TreeNode topNode = childrenStack.pop();
            parentStack.push(topNode);
             
            // Push left and right node into children stack.
            if(topNode.left != null){
                childrenStack.push(topNode.left);
            }
            if(topNode.right != null){
                childrenStack.push(topNode.right);
            }
        }
         
        // Pop element in parent stack and save it into list.
        while(parentStack.size() != 0){
            postorderList.add(parentStack.pop().val);
        }
        return postorderList;
    }

4. 層次遍歷（分層存儲(chǔ)）

層次遍歷是一層一層的從左往右遍歷梳玫，遇到空節(jié)點(diǎn)直接跳過(guò)爹梁，所以可以用兩個(gè)隊(duì)列，一個(gè)隊(duì)列放該層的節(jié)點(diǎn)提澎，一個(gè)隊(duì)列放上個(gè)隊(duì)列所有節(jié)點(diǎn)的孩子姚垃，再倒手。

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> orderTraverseList = new ArrayList<ArrayList<Integer>>();
         
        if(root == null)    return orderTraverseList;
         
        ArrayList<TreeNode> parentList = new ArrayList<TreeNode>();
 
        parentList.add(root);
        
        while(parentList != null && parentList.size() != 0){
            // Add parent node list
            orderTraverseList.add(generateVal(parentList));
            // Generate children node list
            ArrayList<TreeNode> childrenList = generateChildren(parentList);
            //orderTraverseList.add(generateVal(childrenList));
            parentList = childrenList;
        } 
        return orderTraverseList;
    }
     
    public ArrayList<Integer> generateVal(ArrayList<TreeNode> nodeList){
        ArrayList<Integer> valList = new ArrayList<Integer>();
        for(TreeNode node: nodeList){
            valList.add(node.val);
        }
        return valList;
    }
     
    public ArrayList<TreeNode> generateChildren(ArrayList<TreeNode> parentList){
        ArrayList<TreeNode> childrenList = new ArrayList<TreeNode>();
        // Pop nodes in list and save them to current level list.
        for(TreeNode node: parentList){
            // Save all children of nodes in queue1 to queue2
            if(node.left != null){
                childrenList.add(node.left);
            }
            if(node.right != null){
                childrenList.add(node.right);
            }
        }
        return childrenList;
    }

各種奇葩的??

1. 判斷是不是平衡二叉樹

平衡二叉樹就是每個(gè)節(jié)點(diǎn)左右子樹高度差絕對(duì)值不超過(guò)1的二叉樹盼忌，因此先遞歸計(jì)算左右子樹的高度积糯，再判斷當(dāng)前節(jié)點(diǎn)左右子樹高度差是否滿足條件掂墓，若滿足，再對(duì)左右子樹的結(jié)果做與運(yùn)算即可絮宁。

public boolean isBalanced (TreeNode root) {
        // write code here
        if(root == null)    return true;
        int leftTreeHeight = getHeight(root.left);
        int rightTreeHeight = getHeight(root.right);
        if(Math.abs(leftTreeHeight - rightTreeHeight) <= 1){
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }
     
    public int getHeight(TreeNode root){
        if(root == null)    return 0;
        int left = getHeight(root.left) + 1;
        int right = getHeight(root.right) + 1;
        return (left > right) ? left: right;
    }