[数据结构与算法]LeeCode之二叉树

二叉树的前序遍历

/**
 * 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 {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return ret;
        }
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret;
    }
}

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        ret.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        List<Integer> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);

        list.add(root.val);

        List<Integer> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;

    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret =  new ArrayList<>();

        if(root == null){
            return ret;
        }
        List<Integer> leftTree = postorderTraversal(root.left);
        ret.addAll(leftTree);

        List<Integer> rightTree = postorderTraversal(root.right);
        ret.addAll(rightTree);

        ret.add(root.val);
        return ret;

    }
}

二叉树的最大深度（高度）

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return (leftHeight > rightHeight ? leftHeight+1 : rightHeight+1);
    }
}

判断两个树是否相同

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if( p == null && q != null){
            return false;
        }             
        if( 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);
    }
}

判断一个树是不是另一个树的子数

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if( p == null && q != null){
            return false;
        }             
        if( 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);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null || subRoot == null) return false;
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
}

判断一棵树是不是平衡二叉树（时间复杂度为O(n^2)）

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return (leftHeight > rightHeight ? leftHeight+1 : rightHeight+1);
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.abs(left-right) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }
}

判断一棵树是不是平衡二叉树（时间复杂度为O(n)）

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(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) {
        return maxDepth(root) >= 0;
    }
}

判断一棵树是不是对称的

class Solution {
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        // 判断一个树是不是另一个树的子树
        if(leftTree == null && rightTree != null){
            return false;
        }
        if(leftTree != null && rightTree == null){
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
}

牛客 将二叉树变换为源二叉树的镜像。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot == null){
            return null;
        }
        if(pRoot.left == null && pRoot.right == null){
            return pRoot;
        }
         TreeNode tmp = pRoot.left;
         pRoot.left = pRoot.right;
         pRoot.right = tmp;
        if(pRoot.left != null){
           Mirror(pRoot.left);
        }
        if(pRoot.right != null){
            Mirror(pRoot.right);
        }
        return pRoot;
    }
}

二叉树的层次遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size != 0){
                TreeNode top = queue.poll();
                list.add(top.val);
                if(top.left != null){
                    queue.offer(top.left);
                }
                if(top.right != null){
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
}

根据先序遍历的字符串创建二叉树并且以中序遍历输入

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;
    // 借助先序遍历的字符串 以及字符串下标i 创建二叉树
    public static TreeNode createTree(String str){
        if(str == null) return null;
        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 inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
        
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        TreeNode root = createTree(str);
        inorder(root);
    }
}

最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // p 和 q 在根节点两侧 此时root就是最近公共祖先
        // p 或者 q就是根节点 此时最近公共祖先就是 p 或者 q
        if(root == null) return null;
        if(p == null || q == null) return null;
        if(p == root || q == root) return root;
        // 在根节点没有找到 p 或者q 就在根的左边找
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);

        if(leftTree != null && rightTree != null){
            return root;
        }
        if(leftTree != null){
            return leftTree;
        }
        if(rightTree != null){
            return rightTree;
        }
        return null;
    }
}