整理一些关于树的力扣热门算法操作

一、LC94、144、145中序，前序，后续遍历

List<Integer> front = new ArrayList<>();
    List<Integer> mid = new ArrayList<>();
    List<Integer> back = new ArrayList<>();

    //前序遍历
    public void Preorder(TreeNode root){
        if(root == null)
            return;
        front.add(root.val);
        Preorder(root.left);
        Preorder(root.right);
    }

    //中序遍历
    public void Inorder(TreeNode root){
        if(root == null)
            return;
        Inorder(root.left);
        mid.add(root.val);
        Inorder(root.right);
    }

    //后序遍历
    public void Postorder(TreeNode root){
        if(root == null)
            return;
        Postorder(root.left);
        Postorder(root.right);
        back.add(root.val);
    }

二、LC104、111 二叉树最大 最小深度

// 最大深度
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
    
    // 最小深度
    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }else if (root.left == null || root.right == null){
            return 1;
        }else{
            return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
        }
    }

三、LC100 是否同一棵树

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

四、LC101 是否对称二叉树

public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return dfs(root.left,root.right);
    }

    public boolean dfs(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null) return true;
        if(root1==null || root2==null || root1.val != root2.val) return false;
        return dfs(root1.left,root2.right)&&dfs(root1.right,root2.left);
    }

五、LC110 判断平衡二叉树

public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) <=1 ){
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        return false;
    }

    private int maxDepth(TreeNode root){
        if(root==null) return 0;
        return Math.max(getHigh(root.left),getHigh(root.right))+1;
    }

六、LC112 二叉树路径 目标值总和

class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

七、LC226 翻转二叉树

public static TreeNode invertTree(TreeNode root) {
        if (root == null || (root.right == null && root.left == null)){
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

七、判断是否为子树【子树，要么等于，要么等于左/右子树。】

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        //子树，要么等于，要么等于左/右子树。
        return subFrom(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }


    public boolean subFrom(TreeNode root, TreeNode subRoot){
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (root.val != subRoot.val) return false;
        return subFrom(root.left, subRoot.left) && subFrom(root.right, subRoot.right);
    }

八、LC589、590 N叉树的前序 后续遍历

// 前序遍历
class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> preorder(Node root) {
        //递归版
        if(root == null)
            return res;
        res.add(root.val);
        for(Node child : root.children)
        {
            preorder(child);
        }  
        return res;
    }
}

// 后序遍历
class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> postorder(Node root) {
        //递归版
        if(root == null)
            return res;
        
        for(Node child : root.children)
        {
            postorder(child);
        }
        res.add(root.val);
        return res;
    }
}

九、LC559 N叉树的最大深度

public int maxDepth(Node root) {
        if(root == null) return 0;
        int max = 0;
        for(Node node : root.children){
            max = Math.max(maxDepth(node),max);
        }
        return max + 1;
    }

十、Offer27 二叉树的镜像

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

        return root;
    }

十一、NC 是否为二叉搜索树和完全二叉树

public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean bst = isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        boolean ct = isCompeteTree(root);
        return new boolean[]{bst, ct};
    }

    public boolean isBST(TreeNode root, long lower, long upper) {
        if (null == root) return true;
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        return isBST(root.left, lower, root.val) && isBST(root.right, root.val, upper);
    }

    public boolean isCompeteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (queue.peek() != null) {
            TreeNode last = queue.poll();
            queue.offer(last.left);
            queue.offer(last.right);
        }

        while (!queue.isEmpty() && queue.peek() == null) {
            queue.poll();
        }

        return queue.isEmpty();
    }

十二、二叉树的最大路径之和

public class MaxPathSumTree {

    int max =Integer.MIN_VALUE;

    public int maxPathSum (TreeNode root) {
        if (root == null) return 0;
        help(root);
        return max;
    }

    public int help(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //如果子节点为负数节点   让他的计算值为0     则一个节点的最大值为 root+left + right
        int left = Math.max(help(root.left), 0);
        int right = Math.max(help(root.right), 0);
        max = Math.max(max, root.val + left + right);
        return  Math.max(root.val + left, root.val + right);
    }
}

十三、LC404 求二叉树左叶子之和

public static int sumOfLeftLeaves(TreeNode root) {
        int sum = 0;
        if(root == null) return 0;

        if(root.left != null ){
            if(root.left.left == null && root.left.right == null){
                sum += root.left.val;
            }
        }
        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);
        return sum;
    }

十四、LC543 二叉树的最大直径【最大路径长度】

class Solution {
    private int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = dfs(root.left);
        int rightHeight = dfs(root.right);
        max = Math.max(leftHeight + rightHeight, max);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

十五、LC102 二叉树层次优先遍历

// 深度优先遍历：
void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

// 广度优先遍历
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

这个题目层次遍历，应该选用BFS

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

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}