有關二叉樹的一些練習題

二叉樹的第三部分

這一部分 是 有關一些 二叉樹 的 練習題

相同的樹

附上代碼

class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
    
       if(p!= null && q == null || p == null && q != null) {
    
            return false;
        }
        
        if(p == null && q == null ) {
    
            return true;
        }
        if(p.val != q.val) {
    
            return false;
        }
        
       return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

時間複雜度

在來一個 小問題 這 函數 的時間複雜度 為 多少

這裏我們都要遍曆兩顆樹的結點 ，這裏 需要看一下p和 q 的每棵樹的結點個數

這裏求 p 的 結點M 和 q 的 結點樹N 的最小值

0(min(M，N))

看完了相同的 樹那麼接下來 來看 一道類似的題目

另一棵樹的子樹

附上代碼

class Solution {
    
    private boolean isSamTree(TreeNode p,TreeNode q) {
    
        if(p == null && q != null || p != null && q == null) {
    
            return false;
        }
        if(p == null && q == null) {
    
            return true;
        }
        if(p.val != q.val) {
    
            return false;
        }
        return isSamTree(p.left,q.left) && isSamTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    
        if(root == null || subRoot == null) {
    
            return false;
        }
        // 根結點和 subroot是不是兩顆相同的樹
        if(isSamTree(root,subRoot)) {
    
            return true;
        }
        //subRoot 是不是 root 的左子樹
        if(isSubtree(root.left,subRoot)) {
    
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
    
            return true;
        }
        return false;
        
    }
}

時間複雜度

這裏 需要 root 的每個結點 與 subRoot 比較 所以 如果 root 有 S 個結點 subRoot 有 T 個結點，每個 S都需要去 T 比較

所以時間複雜度 就為0(S * N)

平衡二叉樹

附上代碼

class Solution {
    
       public int height(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return Math.max((leftHeight+1),(rightHeight+1));
    }
    // 判斷連個樹是否為 平衡二叉樹
    public boolean isBalanced(TreeNode root) {
    
        if(root == null) {
    
            return true;
        }
        int left = height(root.left);
        int right = height(root.right);
        return    Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}

優化後

class Solution {
    
       public int height(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight >=0 && rightHeight >=0 && Math.abs(leftHeight - rightHeight) <=1) {
    
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
    
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
    
        if(root == null) {
    
            return true;
        }
        return height(root) >=0;
    }
}

對稱二叉樹

附上代碼

class Solution {
    
    //創建一個方法，用來判斷root的左樹和 右數
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
    
        if(leftTree == null && rightTree != null || leftTree != null && rightTree == null) {
    
            return false;
        }
        if(leftTree == null &&rightTree == null) {
    
            return true;
        }
        if(leftTree.val == rightTree.val) {
    
            return isSymmetricChild(leftTree.left,rightTree.right) &&isSymmetricChild(leftTree.right,rightTree.left);
        }
        return false;
    }
    public boolean isSymmetric(TreeNode root) {
    
      if(root == null) return true;
      return isSymmetricChild(root.left,root.right);
    }
}

創建一顆二叉樹

回憶上面我們創建一顆二叉樹是不是 通過 窮舉 來創建的一顆二叉樹，那麼 現在我們來使用先序遍曆來創建一顆二叉樹

二叉樹遍曆

附上代碼

import java.util.Scanner;
import java.util.*;
class TreeNode{
    
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val) {
    
        this.val = val;
    }
}
public class Main{
    
    
    public static int i= 0;
    public static TreeNode createTree(String str) {
    
        
        TreeNode root = null;
        if(str.charAt(i) != '#') {
    
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
    
            i++;
        }
        return root;
    }
    public static void inorter(TreeNode root){
    
        if(root == null) {
    
            return;
        }
        inorter(root.left);
        System.out.print(root.val+" ");
        inorter(root.right);
    }
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        // 這裏需要注意hasNext 與 hasNextLine 的區別
        // hasNextLine 遇到空格不結束
        // hasNext 遇到空格結束
        while(sc.hasNextLine()) {
    
            String str = sc.nextLine();
            TreeNode root = createTree(str);
            inorter(root);
        }
   

​ 最後來補充一下之前的程序 遍曆 ，回憶一下 上文 寫 的 判斷一顆完全二叉樹

其實程序遍曆也是 這個思路 通過 一個隊列，為空 就 不 加入隊列，

程序遍曆

 // 程序遍曆
    public void levelOrder(TreeNode root) {
    
        if(root == null) {
    
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
    
            TreeNode tmp = queue.poll();
            System.out.print(tmp.val+ " ");
            if(tmp.left!= null) {
    
                queue.offer(tmp.left);
            }
            if(tmp.right != null) {
    
                queue.offer(tmp.right);
            }
        }
    }

寫 完了 程序遍曆那麼我們上 力扣 上寫一下oj題嘿嘿

二叉樹的層序遍曆

class Solution {
    
     public List<List<Integer>> levelOrder(TreeNode root) {
    
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        if(root == null) return list;
        while(!queue.isEmpty()) {
    
           int size = queue.size();
            List<Integer> list2 = new ArrayList<>();
            while(size != 0) {
    
                TreeNode tmp = queue.poll();
                list2.add(tmp.val);
                if(tmp.left != null) {
    
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
    
                    queue.offer(tmp.right);
                }
                size--;
            }
            list.add(list2);
        }
        return list;