整理一些關于樹的力扣熱門算法操作

一、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);
        }
    }
}

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;
    }
}

整理一些關于樹的力扣熱門算法操作

一、LC94、144、145中序，前序，後續周遊

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

三、LC100 是否同一棵樹

四、LC101 是否對稱二叉樹

五、LC110 判斷平衡二叉樹

六、LC112 二叉樹路徑目标值總和

七、LC226 翻轉二叉樹

七、判斷是否為子樹【子樹，要麼等于，要麼等于左/右子樹。】

八、LC589、590 N叉樹的前序後續周遊

九、LC559 N叉樹的最大深度

十、Offer27 二叉樹的鏡像

十一、NC 是否為二叉搜尋樹和完全二叉樹

十二、二叉樹的最大路徑之和

十三、LC404 求二叉樹左葉子之和

十四、LC543 二叉樹的最大直徑【最大路徑長度】

十五、LC102 二叉樹層次優先周遊

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

LeetCode-110-平衡二叉樹-C語言

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

LeetCode OJ Binary Tree Right Side View

leetcode809

hdu7108哈希

整理一些關于樹的力扣熱門算法操作

一、LC94、144、145中序，前序，後續周遊

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

三、LC100 是否同一棵樹

四、LC101 是否對稱二叉樹

五、LC110 判斷平衡二叉樹

六、LC112 二叉樹路徑 目标值總和

七、LC226 翻轉二叉樹

七、判斷是否為子樹【子樹，要麼等于，要麼等于左/右子樹。】

八、LC589、590 N叉樹的前序 後續周遊

九、LC559 N叉樹的最大深度

十、Offer27 二叉樹的鏡像

十一、NC 是否為二叉搜尋樹和完全二叉樹

十二、二叉樹的最大路徑之和

十三、LC404 求二叉樹左葉子之和

十四、LC543 二叉樹的最大直徑【最大路徑長度】

十五、LC102 二叉樹層次優先周遊

繼續閱讀

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

六、LC112 二叉樹路徑目标值總和

八、LC589、590 N叉樹的前序後續周遊