算法复习|树

作者: 激扬飞雪 | 来源:发表于2023-01-06 04:46 被阅读0次

今日份打卡 181/365
2020-02-10 周学习计划
环环相扣的计算机基础
贪心算法--最小生成树Prim算法
机器学习算法Code Show——决策树
【金三银四】2022 Android面经实录
【程序员笔试】昨天花了两个小时，今早一个小时整理的树笔试相关
复习算法
算法复习
北航算法复习笔记

95. 不同的二叉搜索树 II

/**
 * 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 {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i = start; i <= end; i++){
            List<TreeNode> leftResult = generateTrees(start, i - 1);
            List<TreeNode> rightResult = generateTrees(i + 1, end);
            for (TreeNode left:leftResult){
                for (TreeNode right:rightResult) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = left;
                    treeNode.right = right;
                    result.add(treeNode);
                }
            }
        }
        return result;
    }
}

98. 验证二叉搜索树

/**
 * 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 {
    private boolean isValidBST(TreeNode root, long max, long min) {
        if (root == null) return true;
        if (root.val >= max || root.val <= min) return false;
        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val);
    }
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return isValidBST(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }
}

99. 恢复二叉搜索树

/**
 * 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 {
    private TreeNode pre;
    private TreeNode t1;
    private TreeNode t2;
    private void traveralsTree(TreeNode root) {
        if (root == null) return;
        traveralsTree(root.left);
        if (pre != null && pre.val > root.val) {
            if (t1 == null) t1 = pre;
            t2 = root;
        }
        pre = root;
        traveralsTree(root.right);
    }
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        traveralsTree(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }
}

100. 相同的树

/**
 * 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 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)  return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); 
    }
}

101. 对称二叉树

/**
 * 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 {
    private boolean isSymmetric(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
}

101. 对称二叉树

/**
 * 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 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-- > 0){
                TreeNode p = queue.poll();
                TreeNode q = queue.poll();
                if (p == null && q == null) continue;
                if (p == null || q == null) return false;
                if (p.val != q.val) return false;
                queue.offer(p.left);
                queue.offer(q.right);
                queue.offer(p.right);
                queue.offer(q.left);
            }
        }
        return true;
    }
}

102. 二叉树的层序遍历

/**
 * 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 {
    private void levelOrder(TreeNode root, int depth, List<List<Integer>> list) {
        if (root == null) return;
        depth++;

        if (list.size() < depth) {
            list.add(new ArrayList<Integer>());
        }
        list.get(depth - 1).add(root.val);
        levelOrder(root.left, depth, list);
        levelOrder(root.right, depth, list);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        levelOrder(root, 0, result);
        return result;
    }
}

105. 从前序与中序遍历序列构造二叉树

/**
 * 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 {
    private HashMap<Integer, Integer> hashMap;
    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart >= preEnd || inStart >= inEnd) return null;
        int val = preorder[preStart];
        int inIndex = hashMap.get(val);
        int inLeft = inIndex - inStart;
        TreeNode treeNode = new TreeNode(val);
        treeNode.left = buildTree(preorder, preStart + 1, preStart + 1 + inLeft, inorder, inStart, inIndex);
        treeNode.right = buildTree(preorder, preStart + 1 + inLeft, preEnd, inorder, inIndex + 1, inEnd);
        return treeNode;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        hashMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++){
            hashMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
}

108. 将有序数组转换为二叉搜索树

/**
 * 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 {
    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left >= right) return null;
        int mid = left + (right - left) / 2;
        TreeNode treeNode = new TreeNode(nums[mid]);
        treeNode.left = sortedArrayToBST(nums, left, mid);
        treeNode.right = sortedArrayToBST(nums, mid + 1, right);
        return treeNode; 
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return sortedArrayToBST(nums, 0, nums.length);
    }
}

109. 有序链表转换二叉搜索树

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * 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 {
    private TreeNode sortedListToBST(ListNode leftNode, ListNode rightNode) {
        if (leftNode == rightNode) return null;
        ListNode fast = leftNode;
        ListNode slow = leftNode;
        while (fast != rightNode && fast.next != rightNode) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode treeNode = new TreeNode(slow.val);
        treeNode.left = sortedListToBST(leftNode, slow);
        treeNode.right = sortedListToBST(slow.next, rightNode);
        return treeNode;
    }
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return sortedListToBST(head, null);
    }
}

110. 平衡二叉树

/**
 * 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 {
    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
}

111. 二叉树的最小深度

/**
 * 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 {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (leftDepth == 0) return rightDepth + 1;
        if (rightDepth == 0) return leftDepth + 1;
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

112. 路径总和

/**
 * 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 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        if (root.left != null) {
            if (hasPathSum(root.left, targetSum - root.val)) return true;
        }

        if (root.right != null) {
            if (hasPathSum(root.right, targetSum - root.val)) return true;
        }

        return false;

    }
}

114. 二叉树展开为链表

/**
 * 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 {
    private TreeNode pre;
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = pre;
        root.left = null;
        pre = root;
    }
}

/**
 * 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 {
    private void flatten(TreeNode root, List<TreeNode> result) {
        if (root == null) return;
        result.add(root);
        flatten(root.left, result);
        flatten(root.right, result);
    }
    public void flatten(TreeNode root) {
        if (root == null) return ;
        List<TreeNode> result = new ArrayList<>();
        flatten(root, result);
        TreeNode pre = result.get(0);
        pre.left = null;
        pre.right = null;
        for (int i = 1; i < result.size(); i++){
            TreeNode cur = result.get(i);
            pre.right = cur;
            cur.left = null;
            cur.right = null;
            pre = cur;
            
        }
    }
}

116. 填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            Node nextNode = null;
            while (size-- > 0) {
                Node node = queue.poll();
                node.next = nextNode;
                nextNode = node;
                if (node.right != null) queue.offer(node.right);
                if (node.left != null) queue.offer(node.left);
            }
        }
        return root;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        if (root.left != null) {
            root.left.next = root.right;
            if (root.next != null) {
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

117. 填充每个节点的下一个右侧节点指针 II

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    private Node getNext(Node root) {
        if (root == null) return root;
        if (root.left != null) return root.left;
        if (root.right != null) return root.right;
        return getNext(root.next);
    }
    public Node connect(Node root) {
        if (root == null) return root;
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }
        if (root.left != null && root.right == null) {
            root.left.next = getNext(root.next);
        }
        if (root.right != null) {
            root.right.next = getNext(root.next);
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
}

145. 二叉树的后序遍历

/**
 * 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 {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (!stack.isEmpty() || cur != null){
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.peek();
                if (node.right == null || pre == node.right) {
                    stack.pop();
                    result.add(node.val);
                    pre = node;
                    cur = null;
                } else {
                    cur = node.right;
                }
            }
        }
        return result;
    }
}

889. 根据前序和后序遍历构造二叉树

/**
 * 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 {
    private HashMap<Integer, Integer> hashMap;
    private TreeNode constructFromPrePost(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) return null;
        if (preStart == preEnd) return new TreeNode(preorder[preStart]);
        int val = preorder[preStart];
        int postIndex = hashMap.get(preorder[preStart + 1]);
        int postLeft = postIndex - postStart + 1;
        TreeNode node = new TreeNode(val);
        node.left = constructFromPrePost(preorder, preStart + 1, preStart + postLeft, postorder, postStart, postIndex);
        node.right = constructFromPrePost(preorder, preStart + postLeft + 1, preEnd, postorder, postIndex + 1, postEnd - 1);
        return node;
    }
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        hashMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++){
            hashMap.put(postorder[i], i);
        }
        return constructFromPrePost(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }
}

222. 完全二叉树的节点个数

/**
 * 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 {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftCount = 0;
        TreeNode leftNode = root.left;
        while (leftNode != null) {
            leftCount++;
            leftNode = leftNode.left;
        }
        int rightCount = 0;
        TreeNode rightNode = root.right;
        while (rightNode != null){
            rightCount++;
            rightNode = rightNode.right;
        }
        if (leftCount == rightCount) {
            return (2 << leftCount) - 1;
        }
        leftCount = countNodes(root.left);
        rightCount = countNodes(root.right);
        return leftCount + rightCount + 1;
    }
}

230. 二叉搜索树中第K小的元素

/**
 * 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 {
    private int num = 0;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return -1;
        int leftVal = kthSmallest(root.left, k);
        if (leftVal >= 0) return leftVal;
        num++;
        if (num == k) return root.val;
        int rightVal = kthSmallest(root.right, k);
        return rightVal;
    }
}

/**
 * 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 {
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return -1;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int num = 0;
        while (!stack.isEmpty() || cur != null){
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }  else {
                TreeNode node = stack.pop();
                num++;
                if (num == k) {
                    return node.val;
                }
                cur = node.right;
            }
        }
        return -1;
    }
}

236. 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        if (root == p || root == q) return root;
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        if (leftNode != null && rightNode != null) return root;
        else if (leftNode != null && rightNode == null) return leftNode;
        else if (leftNode == null && rightNode != null) return rightNode;
        else return null;
    }
}

662. 二叉树最大宽度

/**
 * 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 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        List<Pair<TreeNode, Integer>> list = new ArrayList<>();
        list.add(new Pair<TreeNode, Integer> (root, 0));
        int result = 1;
        while (!list.isEmpty()){
            List<Pair<TreeNode, Integer>> temp = new ArrayList<>();
            for (Pair<TreeNode, Integer> ele:list){
                TreeNode node = ele.getKey();
                int index = ele.getValue();
                if (node.left != null) {
                    temp.add(new Pair<TreeNode, Integer>(node.left, 2 * index + 1));
                }
                
                if (node.right != null) {
                    temp.add(new Pair<TreeNode, Integer>(node.right, 2 * index + 2));
                }
            }
            int width = list.get(list.size() - 1).getValue() - list.get(0).getValue() + 1;
            result = Math.max(result, width);
            list = temp;
        }
        return result;
    }
}

/**
 * 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 {
    int result = 0;
    private void dfs(TreeNode root, int depth, int index, List<Integer> list) {
        if (root == null) return;
        if (depth > list.size()) {
            list.add(index);
        }
        result = Math.max(result, index - list.get(depth - 1) + 1);
        dfs(root.left, depth + 1, 2 * index, list);
        dfs(root.right, depth + 1, 2 * index + 1, list);
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        List<Integer> list = new ArrayList<>();
        dfs(root, 1, 1, list);
        return result;
    }
    
}

297. 二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 import java.util.*;
public class Codec {

    public String serialize(TreeNode root) {
            if (root == null) return "";
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            StringJoiner joiner = new StringJoiner(",");
            joiner.add(root.val + "");
            while (!queue.isEmpty()){
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                    joiner.add(node.left.val + "");
                } else {
                    joiner.add("null");
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    joiner.add(node.right.val + "");
                } else {
                    joiner.add("null");
                }
            }
            String result =  joiner.toString();
            System.out.println(result);
            return result;
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || "".equals(data)) return  null;
            String[] nodes = data.split(",");
            TreeNode head = new TreeNode(Integer.parseInt(nodes[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(head);
            int index = 1;
            int len = nodes.length;
            while (index < len){
                TreeNode node  = queue.poll();
                if (!"null".equals(nodes[index])) {
                    TreeNode leftNode = new TreeNode(Integer.parseInt(nodes[index]));
                    node.left = leftNode;
                    queue.offer(leftNode);
                }
                index++;
                if (index < len && !"null".equals(nodes[index])) {
                    TreeNode rightNode = new TreeNode(Integer.parseInt(nodes[index]));
                    node.right = rightNode;
                    queue.offer(rightNode);
                }
                index++;
            }
            return  head;
        }
}

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    private void toStr(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("null,");
            return;
        }
        sb.append(root.val + ",");
        toStr(root.left, sb);
        toStr(root.right, sb);
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return null;
        StringBuilder sb = new StringBuilder();
        toStr(root, sb);
        String result = sb.toString();
        System.out.println(result);
        return result;
    }
    
    private int index = 0;
    private TreeNode toTree(String[] nodes){
        if ("null".equals(nodes[index])) {
            index++;
            return null;
        }
        TreeNode treeNode = new TreeNode(Integer.parseInt(nodes[index]));
        index++;
        treeNode.left = toTree(nodes);
        treeNode.right = toTree(nodes);
        return treeNode;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || "".equals(data)) return null;
        String[] nodes = data.split(",");
        index = 0;
        return toTree(nodes);
    }

}

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

331. 验证二叉树的前序序列化

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || "".equals(preorder)) return true;
        String[] nodes = preorder.split(",");
        int length = nodes.length;
        if ("#".equals(nodes[0]) && length > 1) return false;
        if ("#".equals(nodes[0])) return true;
        int i = 0;
        Stack<String> stack = new Stack<>();
        while (i < length) {
            String node = nodes[i];
            if (!"#".equals(node)) {
                stack.push(node);
                i++;
            } else {
                if (!stack.isEmpty() && "#".equals(stack.peek())) {
                    stack.pop();
                    if (stack.isEmpty()) return false;
                    stack.pop();
                } else {
                    //
                    stack.push(node);
                    i++;
                }
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

class Solution {
    private int index;
    private boolean dfs(String[] nodes) {
        if (index >= nodes.length) return false;
        if ("#".equals(nodes[index])) {
            index++;
            return true;
        }
        index++;
        return dfs(nodes) && dfs(nodes);
    }
    public boolean isValidSerialization(String preorder) {
        if ("".equals(preorder)) return true;
        String[] nodes = preorder.split(",");
        index = 0;
        boolean result = dfs(nodes);
        
        return index == nodes.length && result;
    }
}

543. 二叉树的直径

/**
 * 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 {
    int result = 0;
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = dfs(root.left); 
        int rightHeight = dfs(root.right);
        result = Math.max(leftHeight + rightHeight,result);
        return Math.max(leftHeight, rightHeight) + 1;
    }
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return result;
    }
}

124. 二叉树中的最大路径和

/**
 * 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 {
    private int result = Integer.MIN_VALUE;
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int leftV = Math.max(dfs(root.left), 0);
        int rightV = Math.max(dfs(root.right), 0);
        result = Math.max(result, root.val + leftV + rightV);
        return root.val + Math.max(leftV, rightV);
    }
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return result;
    }
}

958. 二叉树的完全性检验

/**
 * 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 {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = false;
        while (!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            if (treeNode == null) {
                flag = true;
                continue;
            }
            if (flag) return false;
            queue.offer(treeNode.left);
            queue.offer(treeNode.right);
        }

        return true;
    }
}

今日份打卡 181/365
技术文章最小生成树算法复习prim算法
2020-02-10 周学习计划
1、复习K近邻算法，总结到公众号； 2、复习决策树算法，总结到公众； 3、学习集智学园-张江老师-netlogo...
环环相扣的计算机基础
为了写多路归并的算法，不得不去看胜者树败者树；为了看胜者败者树，去复习了堆排序算法；为了温习堆排序，不得不看了选择...
贪心算法--最小生成树Prim算法
引言：前两天在复习贪心算法时，看到单源最短路径的Dijkstra算法和最小生成树的Prim算法，由于自己不认真，竟...
机器学习算法Code Show——决策树
上一篇文章机器学习算法复习手册——决策树在复习完基本概念之后，我给自己挖了一个坑：用python写一个决策树出来（...
【金三银四】2022 Android面经实录
复习点具体链接 1 算法部分打遍天下二叉树 https://github.com/xfhy/Android-N...
【程序员笔试】昨天花了两个小时，今早一个小时整理的树笔试相关
算法+数据结构+树按照复习顺序记录 2018年07月18日``09:11 遍历转2叉度具体应用 ----...
复习算法
My personal study notes for learning Algorithhms 4th Edit...
算法复习
1、冒泡排序 2、二分查找 3、判断回文：解法一(切片)、解法二（双指针） 4、基于排列构建数组 5、数组串联...
北航算法复习笔记
#算法复习笔记一决策和策略二回溯法使用深度优先（dfs）搜索状态空间树三快速排序标准（常用）快速排序...

算法复习|树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读