[数据结构与算法]搞搞算法 2: 二叉树

参考：https://github.com/labuladong/fucking-algorithm

二叉树

力扣104 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

方法一：遍历二叉树

class Solution {
? ? // 当前深度
? ? int depth = 0;
? ? // 最大深度
? ? int res = 0;

? ? /**
   ? * 主方法
?    */
? ? public int maxDepth(TreeNode root) {
? ? ? ? traverse(root);
? ? ? ? return res;
? ? }

? ? /**
? ? ?* 遍历二叉树
? ? ?*/
? ? public void traverse(TreeNode root){
? ? ? ? if(root == null){
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? // 前序位置
? ? ? ? depth++;
? ? ? ? if(root.left == null && root.right == null){
? ? ? ? ? ? res = Math.max(depth, res);
? ? ? ? }
? ? ? ? // 处理左子树
? ? ? ? traverse(root.left);
? ? ? ? // 中序位置(无内容)
? ? ? ? // 处理右子树
? ? ? ? traverse(root.right);
? ? ? ? // 后序位置
? ? ? ? depth--;
? ? }
}

方法二：问题分解

class Solution {
? ? public int maxDepth(TreeNode root) {
? ? ? ? if(root == null){
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? // 处理左子树
? ? ? ? int leftDepth = maxDepth(root.left);
? ? ? ? // 处理右子树
? ? ? ? int rightDepth = maxDepth(root.right);
? ? ? ? return Math.max(leftDepth, rightDepth) + 1;
? ? }
}

力扣543 二叉树的直径

https://leetcode.cn/problems/diameter-of-binary-tree/

class Solution {
? ? // 二叉树的直径
? ? int res = 0;

? ? // 主方法
? ? public int diameterOfBinaryTree(TreeNode root) {
? ? ? ? depthOfBinaryTree(root);
? ? ? ? return res;
? ? }

? ? /**
? ? ?* 二叉树的深度
? ? ?*/
? ? public int depthOfBinaryTree(TreeNode root){
? ? ? ? if(root == null){
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? int leftDepth = depthOfBinaryTree(root.left);
? ? ? ? int rightDepth = depthOfBinaryTree(root.right);
? ? ? ? // 顺便计算二叉树的直径
? ? ? ? res = Math.max(res, leftDepth + rightDepth);
? ? ? ? return Math.max(leftDepth, rightDepth) + 1;
? ? }
}

力扣226 翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/

方法一：遍历二叉树

class Solution {
? ? /**
? ? ?* 主方法
? ? ?*/
? ? public TreeNode invertTree(TreeNode root) {
? ? ? ? traverse(root);
? ? ? ? return root;
? ? }

? ? /**
? ? ?* 遍历二叉树
? ? ?*/
? ? public void traverse(TreeNode root){
? ? ? ? if(root == null){
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? TreeNode tn = root.left;
? ? ? ? root.left = root.right;
? ? ? ? root.right = tn;
? ? ? ? traverse(root.left);
? ? ? ? traverse(root.right);
? ? }
}

方法二：问题分解

class Solution {
? ? public TreeNode invertTree(TreeNode root) {
? ? ? ? if(root == null){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? TreeNode tn = invertTree(root.left);
? ? ? ? root.left = invertTree(root.right);
? ? ? ? root.right = tn;
? ? ? ? return root;
? ? }
}

力扣116 填充每个结点的下一个右侧结点指针

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

class Solution {
????/**
?????*?主方法
?????*/
? ? public Node connect(Node root) {
? ? ? ? if(root == null){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? traverse(root.left, root.right);
? ? ? ? return root;
? ? }

    /**
     * 遍历二叉树
     */
? ? public void traverse(Node left, Node right){
? ? ? ? if(left == null || right == null){
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? left.next = right;
? ? ? ? traverse(left.left, left.right);
? ? ? ? traverse(right.left, right.right);
? ? ? ? // 连接左右子树
? ? ? ? traverse(left.right, right.left);
? ? }
}

力扣114 二叉树展开为链表

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        // 处理左子树
        flatten(root.left);
        // 处理右子树
        flatten(root.right);
        // 处理当前结点
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = left;
        TreeNode tn = root;
        while(tn.right != null){
            tn = tn.right;
        }
        tn.right = right;
    }
}

力扣654 最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/

class?Solution?{
????/**
?????*?主方法
?????*/
????public?TreeNode?constructMaximumBinaryTree(int[]?nums){
????????return?constructMaximumBinaryTree(nums,?0,?nums.length?-?1);
????}

????/**
?????*?构造最大二叉树
?????*/
????public?TreeNode?constructMaximumBinaryTree(int[]?nums,?int?start,?int?end)?{
????????if(start?>?end){
????????????return?null;
????????}
????????int?maxValueIndex?=?getMaxValueIndex(nums,?start,?end);
????????TreeNode?root?=?new?TreeNode(nums[maxValueIndex]);
????????root.left?=?constructMaximumBinaryTree(nums,?start,?maxValueIndex?-?1);
????????root.right?=?constructMaximumBinaryTree(nums,?maxValueIndex?+?1,?end);
????????return?root;
????}

????/**
?????*?获取最大值对应的数组下标
?????*/
????public?int?getMaxValueIndex(int[]?nums,?int?start,?int?end){
????????int?index?=?-1;
????????int?maxValue?=?Integer.MIN_VALUE;
????????for(int?i?=?start;?i?<=?end;?i++){
????????????if(nums[i]?>?maxValue){
????????????????index?=?i;
????????????????maxValue?=?nums[i];
????????????}
????????}
????????return?index;
????}
}

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

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

class?Solution?{
????Map<Integer,?Integer>?valToIndexMap?=?new?HashMap();

????/**
?????*?主方法
?????*/
????public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{
????????for?(int?i?=?0;?i?<?inorder.length;?i++)?{
????????????valToIndexMap.put(inorder[i],?i);
????????}
????????return?build(preorder,?inorder,?0,?preorder.length?-?1,?0,?inorder.length?-?1);
????}

????/**
?????*?构造二叉树
?????*/
????public?TreeNode?build(int[]?preorder,?int[]?inorder,?int?preLeft,?int?preRight,?int?inLeft,?int?inRight){
????????if(preLeft?>?preRight){
????????????return?null;
????????}
????????TreeNode?root?=?new?TreeNode(preorder[preLeft]);
????????int?index?=?valToIndexMap.get(preorder[preLeft]);

????????root.left?=?build(preorder,?inorder,?preLeft?+?1,?preLeft?+?(index?-?inLeft),?inLeft,?index?-?1);
????????root.right?=?build(preorder,?inorder,?preLeft?+?(index?-?inLeft)?+?1,?preRight,?index?+?1,?inRight);
????????return?root;
????}
}

力扣106 从中序与后序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

class?Solution?{
????Map<Integer,?Integer>?valToIndexMap?=?new?HashMap();

????/**
?????*?主方法
?????*/
????public?TreeNode?buildTree(int[]?inorder,?int[]?postorder)?{
????????for?(int?i?=?0;?i?<?inorder.length;?i++)?{
????????????valToIndexMap.put(inorder[i],?i);
????????}
????????return?build(inorder,?postorder,?0,?inorder.length?-?1,?0,?postorder.length?-?1);
????}
????/**
?????*?构造二叉树
?????*/
????public?TreeNode?build(int[]?inorder,?int[]?postorder,?int?inLeft,?int?inRight,?int?postLeft,?int?postRight){
????????if(inLeft?>?inRight){
????????????return?null;
????????}
????????TreeNode?root?=?new?TreeNode(postorder[postRight]);
????????int?index?=?valToIndexMap.get(postorder[postRight]);
????????root.left?=?build(inorder,?postorder,?inLeft,?index?-?1,?postLeft,?postLeft?+?(index?-?inLeft)?-?1);
????????root.right?=?build(inorder,?postorder,?index?+?1,?inRight,?postLeft?+?(index?-?inLeft),?postRight?-?1);
????????return?root;
????}
}