二叉樹的定義及相關(guān)性質(zhì)

二叉樹性質(zhì)及操作

注意：對于String來說，length()是一個方法，必須加括號
而對于數(shù)組來說，length只是數(shù)組的父類Array從Object哪里繼承過來的屬性，所以是類的屬性，就不需要加括號

劍指offer 07 重建二叉樹

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;   //將preorder 變成全局變量， recur中可直接調(diào)用

        //將inorder裝入HashMap中，方便后面查找root
        for(int i=0; i<inorder.length; i++){
            dic.put(inorder[i],i);
        }
        return recur(0,0,inorder.length - 1);
    }
    /**
    * 利用inorder的最左和最右node分別在list中的第一和最后一個，不斷地迭代遍歷整個樹
    * @param root_preIndx root在preorder中的index
    * @param left_inIndx  整個樹的最左node在inorder中的index
    * @param right_inIndx 整個樹的最右node在inorder中的index
    * @return 當(dāng)前樹的root
    */
    public TreeNode recur (int root_preIndx, int left_inIndx, int right_inIndx){
        //當(dāng)最左node的index大于最右node的index， 即已經(jīng)遍歷完
        if(left_inIndx > right_inIndx){
            return null; 
        }

        TreeNode node = new TreeNode(preorder[root_preIndx]);
        int root_inIndx = dic.get(preorder[root_preIndx]);  //查詢root在inorder中的index
        //node.left = 左子樹的root
        node.left = recur(root_preIndx + 1, left_inIndx, root_inIndx - 1);

        //求出左子樹在inorder中長度len_left，node.right在preorder中的index = root_preIndx + len_left
        int len_left = root_inIndx - left_inIndx + 1;
        node.right = recur(root_preIndx + len_left, root_inIndx + 1, right_inIndx);

        return node;
    }
}

劍指offer 26 樹的子結(jié)構(gòu)
若樹B是樹A的子結(jié)構(gòu)，樹A節(jié)點為M，樹B節(jié)點為N， 則
時間復(fù)雜度O(MN)
空間復(fù)雜度O(M)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        if (treeCompare(A,B)) return true;
        else return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

//開始對比子樹
    public boolean treeCompare(TreeNode A, TreeNode B){
        // 第一次是不會進(jìn)來，因為上面調(diào)用條件是A,B同時不為null
        // 之后再進(jìn)來的前提則是A,B root 相同，對比child
        if (B == null) return true;

        //如果B == null 且 A != null 說明B 沒結(jié)束但A結(jié)束了 則肯定為false
        if (A == null) return false;

        if (A.val == B.val){
            return treeCompare(A.left,B.left) && treeCompare(A.right,B.right);
        }
        else return false;    
    }
}

劍指offer 27 二叉樹的鏡像
時間復(fù)雜度O(N)
空間復(fù)雜度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        // 暫存左子樹
        TreeNode temp = root.left;
        // 遞歸
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        //當(dāng)無子節(jié)點時，返回節(jié)點本身
        return root;
    }
}

劍指offer 28 對稱的二叉樹
時間復(fù)雜度O(N)
空間復(fù)雜度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isEqual(mirrorTree(root.right),root.left);
        }

    public TreeNode mirrorTree(TreeNode root){
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }

    public boolean isEqual(TreeNode A, TreeNode B){
        if(A == null && B == null) return true;
        if(A == null && B != null) return false;
        if(A != null && B == null) return false;
        if(A.val != B.val) return false;
        return isEqual(A.left,B.left) && isEqual(A.right,B.right);
    }
}

劍指offer 32 從上到下打印二叉樹

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        // 注意：LinkedList,雙大寫
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.add(root);

        //注意：isEmpty()
        while(!queue.isEmpty()){
           TreeNode node = queue.poll();
           list.add(node.val);
           if(node.left != null) queue.add(node.left);
           if(node.right != null) queue.add(node.right);
        }
        int[] ans = new int[list.size()];
        // 括號之間用“;”隔開
        for(int i = 0; i<list.size(); i++){
            ans[i] = list.get(i);
        }

        return ans;
    }
}

劍指offer 32-ii 從上到下打印二叉樹 ii

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        // 當(dāng)root為null是，List也為null

        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();

            //注意：此時應(yīng)從queue的size開始遞減,size為0時，queue為空
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }

            ans.add(temp);
        }

        return ans;
    }
}

劍指offer 32-iii 從上到下打印二叉樹 iii
基本思路： queue的存儲順序不變，根據(jù)奇偶行，在組temp時進(jìn)行前插或順序排列，進(jìn)而達(dá)到改變偶行讀取順序

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        int level = 1;

        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            LinkedList<Integer> temp = new LinkedList<>();
            int rem = level % 2;

            if(rem == 0){
                for(int i = queue.size(); i>0; i--){
                    TreeNode node = queue.poll();
                    // 偶行 從右至左
                    temp.addFirst(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);  
                }
            }
            else{
                for(int i = queue.size(); i>0; i--){
                    TreeNode node = queue.poll();
                    temp.add(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
            }
            ans.add(temp);
            level++;
        }
        return ans;
    }
}

劍指offer 33 二叉搜索樹的后序遍歷序列
基本思路：1.數(shù)列中最后一位是root
?????2.從左至右找出第一個比root大的node，位置記作temp（之后為右子樹，之前為左子樹）
?????3. temp之后若出現(xiàn)小于root，則為false

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 數(shù)組 length不需要括號
        return orderCheck(postorder, 0, postorder.length-1);
    }

    public boolean orderCheck(int[] postorder, int left, int right){
        // 需要先判斷l(xiāng)eft 和 right 大小關(guān)系，否則會超出范圍
        if(left >= right) return true;
        int root = postorder[right];
        int firstLarge = left;

        // 找第一個大于root的節(jié)點
        while(postorder[firstLarge] < root){
            firstLarge++;
        }

        // 判斷之后是否都大于root
        for(int temp = firstLarge; temp < right; temp++){
            if(postorder[temp] < root) return false;
        }
        
        return orderCheck(postorder, left, firstLarge-1) && orderCheck(postorder, firstLarge, right-1);
        
    }
}

劍指offer 34 二叉樹中和為某一值的路徑
經(jīng)典回溯問題

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 必須寫在外面，否則方法內(nèi)不能調(diào)用
    public List<List<Integer>> ans = new ArrayList<>();
    public LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        helper(root,sum);
        return ans;
    }

    //返回類型是void 空型 這里面如果return語句返回一個值的話會報錯，
    //如果就只是一個return;表示程序結(jié)束不繼續(xù)往下執(zhí)行。
    public void helper(TreeNode root, int sum){
        if(root == null) return;
        sum -= root.val;
        list.add(root.val);

        if(root.left == null && root.right == null && sum == 0){
            // 值得注意的是，記錄路徑時若直接執(zhí)行 ans.add(list) 則是將 list 對象加入了 ans ；
            //后續(xù) list 改變時 ans 中的 list 對象也會隨之改變。
            //正確做法：ans.add(new ArrayList(list)) 相當(dāng)于復(fù)制了一個 list 并加入到 ans
            ans.add(new ArrayList<>(list));
            // 這里不加remove和return的目的是，接下來的子node都是null，下一步自動return

        }
        helper(root.left,sum);
        helper(root.right,sum);
        // remove目的是不改變 public list
        list.removeLast();
    }
}

劍指offer 55i 二叉樹的深度
第一個完全一次作對的題目 :) 加油，別放棄

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

劍指offer 55ii 平衡二叉樹

當(dāng)左右平衡但子樹不平衡時

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(getDeepth(root) == -1) return false;
        return true;
    }
    public int getDeepth(TreeNode root){
        if(root == null) return 0;
        int leftDeepth = getDeepth(root.left);
        int rightDeepth = getDeepth(root.right);
        // 計算root的左右兩邊是否高度差是否大于1
        if(Math.abs(leftDeepth - rightDeepth) > 1) return -1;
        // 計算 左右子樹 的高度差是否大于1
        if(rightDeepth == -1 || leftDeepth == -1) return -1;
        
        return Math.max(leftDeepth,rightDeepth) + 1;
    }
}

劍指offer 37 序列化二叉樹
第一次挑戰(zhàn)困難的題，能夠讀懂并且寫明了。 又進(jìn)了一步，加油 :)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    TreeNode node;
    // Encodes a tree to a single string.
    // 雖然可以直接拼接字符串，但是，在循環(huán)中，每次循環(huán)都會創(chuàng)建新的字符串對象，
    //然后扔掉舊的字符串。這樣，絕大部分字符串都是臨時對象，不但浪費內(nèi)存，還會影響GC效率。
    public String serialize(TreeNode root) {
        if(root == null) return "null";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            // 1. 勿忘"null,"逗號  2. continue的作用：避免null上加null
            if(node == null) {
                sb.append("null,");
                continue;
                }
            sb.append(node.val + ",");
            queue.add(node.left);
            queue.add(node.right);
        }
        // 一定要toString();因為return的type是string
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "null") return null;
        String[] str = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        queue.add(root);
        for(int i = 1;i < str.length; i++){
            /*
                1
               / \
              2   3
                 / \
                4   5
            當(dāng)node 2沒有child時，會被從queue中拿出然后 i += 1; 進(jìn)行下一個node
                */
            TreeNode parent = queue.poll();
            if(!"null".equals(str[i])){
                TreeNode left = new TreeNode(Integer.parseInt(str[i]));
                parent.left = left;
                queue.add(left);
            }
            i += 1;
            if(!"null".equals(str[i])){
                TreeNode right = new TreeNode(Integer.parseInt(str[i]));
                parent.right = right;
                queue.add(right);
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

劍指offer 54 二叉搜索書的第k大節(jié)點

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int k;
    private int ans;
    public int kthLargest(TreeNode root, int k) {
        if(root == null) return 0;
        this.k = k;
        traversal(root);
        return ans;
    }
    // 右 根 左
    public void traversal(TreeNode root){
        if(root == null) return;
        traversal(root.right);
        
        if(--this.k == 0)  this.ans = root.val;
        traversal(root.left);
    }
}