数据结构-树及相关算法

 /* 二叉树遍历框架 */
 void traverse(TreeNode root) {
     // 前序遍历
     traverse(root.left)
     // 中序遍历
     traverse(root.right)
     // 后序遍历
 }

 ​
 public TreeNode invertTree(TreeNode root) {
         if (root == null) {
         return root;
     }
     //翻转
     TreeNode tempNode = root.left;
     root.left = root.right;
     root.right = tempNode;
     //子节点也去翻转
     invertTree(root.left);
     invertTree(root.right);
     return root;
 }

 // 主函数
 Node connect(Node root) {
     if (root == null) return null;
     connectTwoNode(root.left, root.right);
     return root;
 }
 ​
 // 辅助函数
 void connectTwoNode(Node node1, Node node2) {
     if (node1 == null || node2 == null) {
         return;
     }
     /**** 前序遍历位置 ****/
     // 将传入的两个节点连接
     node1.next = node2;
 ​
     // 连接相同父节点的两个子节点
     connectTwoNode(node1.left, node1.right);
     connectTwoNode(node2.left, node2.right);
     // 连接跨越父节点的两个子节点
     connectTwoNode(node1.right, node2.left);
 }

 // 定义：将以 root 为根的树拉平为链表
 void flatten(TreeNode root) {
     // base case
     if (root == null) return;
 ​
     flatten(root.left);
     flatten(root.right);
 ​
     /**** 后序遍历位置 ****/
     // 1、左右子树已经被拉平成一条链表
     TreeNode left = root.left;
     TreeNode right = root.right;
 ​
     // 2、将左子树作为右子树
     root.left = null;
     root.right = left;
 ​
     // 3、将原先的右子树接到当前右子树的末端
     TreeNode p = root;
     while (p.right != null) {
         p = p.right;
     }
     p.right = right;
 }

 public TreeNode constructMaximumBinaryTree(int[] nums) {
         return test(nums, 0, nums.length - 1);
     }
 ​
     public TreeNode test(int[] nums, int start, int end){
         if (start > end) {
             return null;
         }
         int index = start;
         int max = nums[start];
         for (int i = start + 1; i <= end; i++) {
             if (max < nums[i]) {
                 max = nums[i];
                 index = i;
             }
         }
         TreeNode node = new TreeNode(max);
 ​
         node.left = test(nums, start, index - 1);
         node.right = test(nums, index +1, end);
         return node;
     }

 class Solution {
     public TreeNode buildTree(int[] preorder, int[] inorder) {
         return test(preorder, 0, preorder.length -1 , inorder, 0 , inorder.length-1);
     }
 ​
     public TreeNode test(int[] preorder,int prestart, int preend, int[] inorder, int instart, int inend) {
         if (prestart > preend) {
             return null;
         }
         int index = 0;
         for (int i = instart; i <= inend; i++) {
             if (preorder[prestart] == inorder[i]) {
                 index = i;
                 break;
             }
         }
         TreeNode node = new TreeNode(preorder[prestart]);
         int size = index - instart;
         node.left = test(preorder, prestart + 1, size + prestart, inorder, instart, index -1);
         node.right = test(preorder, size +prestart + 1, preend, inorder, index + 1, inend);
         return node;
     }
 }

 class Solution {
     public TreeNode buildTree(int[] inorder, int[] postorder) {
         return build(inorder, 0, inorder.length-1, postorder, postorder.length - 1, 0);
     }
 ​
     public TreeNode build(int[] inorder,int instart, int inend, int[] postorder, int postend, int poststart) {
         if (postend < poststart) {
             return null;
         }
         int index = 0;
         for (int i = 0; i < inorder.length; i++) {
             if (postorder[postend] == inorder[i]) {
                 index = i;
                 break;
             }
         }
         int size = index - instart;
         TreeNode node = new TreeNode(postorder[postend]);
         node.left = build(inorder, instart, index - 1, postorder, poststart + size-1, poststart);
         node.right = build(inorder, index + 1, inend, postorder, postend - 1, poststart +size);
 ​
         return node;
     }
 }

 class Solution {
     public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
         if (root == null) {
             return null;
         }
         findMap(root);
   
         return list;
     }
     Map<String, Integer> map = new HashMap<>();
     List<TreeNode> list = new ArrayList<>();
 ​
     public String findMap(TreeNode root){
         if (root == null) {
             return "#";
         }
         String s1 = findMap(root.left);
         String s2 = findMap(root.right);
         String s = root.val+"," + s1+"," + s2;
         if (map.containsKey(s)) {
             if (map.get(s) == 1) {
                 list.add(root);
             }
             map.put(s, map.get(s) + 1);
         }else {
             map.put(s, 1);
         }
         return s;
     }
 }

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null) return null;
    if (root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 情况 1
    if (left != null && right != null) {
        return root;
    }
    // 情况 2
    if (left == null && right == null) {
        return null;
    }
    // 情况 3
    return left == null ? right : left;
}

/**
	 * 普通二叉树计算节点总数
	 * @param node
	 * @return
	 */
	public static int getCount1(TreeNode node) {
		if (node == null) {
			return 0;
		}
		return 1 + getCount1(node.left) + getCount1(node.right);
	}
	/**
	 * 满二叉树计算节点总数, 满二叉树就是每一层的节点数都是满的
	 * @param node
	 * @return
	 */
	public static int getCount2(TreeNode node) {
		int high = 0;
		while (node != null) {
			high ++;
			node = node.left;
		}
		return (int)Math.pow(2, high) - 1;
	}
	/**
	 * 计算完全二叉树的节点总数
	 * @param node
	 * @return
	 */
	public static int getCount3(TreeNode node) {
		TreeNode lNode = node;
		TreeNode rNode = node;
		int l = 0;
		while (lNode != null) {
			l ++;
			lNode = lNode.left;
		}
		int r = 0;
		while (rNode != null) {
			l ++;
			rNode = rNode.left;
		}
		if (l == r) {
			return (int)Math.pow(2, l) - 1;
		}
		return 1+getCount3(node.left) + getCount3(node.right);
	}

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

public boolean isValidBST(TreeNode root) {
		return judge(root, null, null);
    }
	/**
	 * 要求：max.min > root.val > min.val
	 * @param root
	 * @param min
	 * @param max
	 * @return
	 */
	public boolean judge(TreeNode root, TreeNode min, TreeNode max) {
		if (root == null) {
			return true;
		}
		if (min != null && min.val >= root.val) {
			return false;
		}
		if (max != null && max.val <= root.val) {
			return false;
		}
		return judge(root.left, min, root) && judge(root.right, root, max);
	}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
		if (root == null) {
			return null;
		}
        if (root.val == key) {
			//删除 分为两种删除，在末尾直接删除，在中间(左右都存在和存在一个孩子)就要判断了
        	if (root.left == null && root.right == null) {
				return null;
			}
        	if (root.left == null || root.right == null) {
				if (root.left == null) {
					return root.right;
				}else {
					return root.left;
				}
			}
        	//左右孩子都存在
        	//首先找到右子树中最小的节点
        	TreeNode minNode = getMin(root.right);
        	//删除最小的节点
        	root.right = deleteNode1(root.right, minNode.val);
        	root.val = minNode.val;
		}else if(root.val > key) {
			root.left = deleteNode(root.left, key);
		}else {
			root.right = deleteNode(root.right, key);
		}
        return root;
    }

	public TreeNode getMin(TreeNode node) {
		if (node.left == null) {
			return node;
		}
		return getMin(node.left);
	}

	public TreeNode deleteNode1(TreeNode node, int val) {
		if (node == null) {
			return null;
		}
        if (node.val == val) {
			if (node.right != null) {
				return node.right;
			}
			return null;
		}else if(node.val > val) {
			node.left = deleteNode1(node.left, val);
		}
        return node;
	}
}

class Solution {
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs(Node root) {
        if(root == null){
            return;
        }
        dfs(root.left);
        if (pre == null){
            head = root;
        }else{
            pre.right = root;
        }
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}

public class Codec {

    // Encodes a tree to a single string.
    public  String serialize(TreeNode root) {
        if (root == null) {
			return "#";
		}
        String str = root.val+",";
        String left = serialize(root.left);
        String right =  serialize(root.right);
        str = str + left + "," + right;
        return str;
    }

    // Decodes your encoded data to tree.
    LinkedList<Integer> linkedList = new LinkedList<>();
    public  TreeNode deserialize(String data) {
    	String[] arr = data.split(",");
    	for (String string : arr) {
    		if (string.equals("#")) {
				linkedList.add(null);
			}else {
				linkedList.add(Integer.parseInt(string));
			}
		} 
        return getTreeNode();
    }
    public  TreeNode getTreeNode() {
    	if (linkedList.isEmpty()) {
			return null;
		}
    	Integer numInteger = linkedList.removeFirst();
    	if (numInteger == null) {
			return null;
		}
    	TreeNode rootNode = new TreeNode(numInteger);
    	rootNode.left = getTreeNode();
    	rootNode.right = getTreeNode();
    	return rootNode;
    }
}

void traverse(TreeNode root) {
    if (root == null) return;
    // 初始化队列，将 root 加入队列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode cur = q.poll();

        /* 层级遍历代码位置 */
        System.out.println(root.val);
        /*****************/

        if (cur.left != null) {
            q.offer(cur.left);
        }

        if (cur.right != null) {
            q.offer(cur.right);
        }
    }
}

public static String serialize(TreeNode root) {
        if (root == null) {
			return "#";
		}
        String str = "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
			TreeNode curNode = queue.poll();
			if (curNode == null) {
				str += "#,";
				continue;
			}
			str += curNode.val + ",";
			queue.offer(curNode.left);
			queue.offer(curNode.right);

		}
        return str;
    }

static LinkedList<TreeNode> linkedList = new LinkedList<>();
    public static TreeNode deserialize(String data) {
    	String[] arr = data.split(",");
    	for (String string : arr) {
    		if (string.equals("#")) {
				linkedList.add(null);
			}else {
				linkedList.add(new TreeNode(Integer.parseInt(string)));
			}
		} 
        return getTreeNode();
    }
    public static TreeNode getTreeNode() {
    	Queue<TreeNode> queue1 = new LinkedList<>();
    	TreeNode node = linkedList.poll();
    	queue1.offer(node);
    	while (!queue1.isEmpty()) {
			TreeNode root = queue1.poll();
			root.left = linkedList.poll();
			root.right = linkedList.poll();
			if (root.left != null) {
				queue1.offer(root.left);
			}
			if (root.right != null) {
				queue1.offer(root.right);
			}
		}
    	return node;
  
    }

class NestedInteger {
    Integer val;
    List<NestedInteger> list;
}

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);

 /**
     * 构建赫夫曼树
     * @param arr  要构建的赫夫曼树的叶子结点的权值数组
     * @return 返回赫夫曼树的头结点
     */
    public static TreeNode createHuffmanTree(int[] arr){
        List<TreeNode> nodes = new ArrayList<>();
        for (int i : arr) {
            nodes.add(new TreeNode(i));
        }

        while (nodes.size() > 1){
            //1，排序从小到大
            nodes.sort(Comparator.comparingInt(x -> x.val));
            //取出根节点最小的两颗树
            TreeNode left = nodes.get(0);
            TreeNode right = nodes.get(1);
            //构建一个新的二叉树
            TreeNode parent = new TreeNode(left.val + right.val);
            parent.left = left;
            parent.right = right;
            //从list中删除处理过的二叉树
            nodes.remove(left);
            nodes.remove(right);
            //将parent放入list中
            nodes.add(parent);
        }
        System.out.println(nodes);
        return nodes.get(0);
    }
//输入：{32，2，42}
//结果：
/**
          76
       34    42
     2   32
*/