Java教程

binary tree解题模板

本文主要是介绍binary tree解题模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

基础的三个模板:traverse, dc, bst
【dc模板】
题:108 Convert Sorted Array to Binary Search Tree数组变成高度平衡的二叉树

public TreeNode helper(int[] nums, int low, int high) {

root.left = helper(nums, low, mid - 1);
root.right = helper(nums, mid + 1, high);
}

 

【左右模板】
题:对称二叉树 · symmetric binary tree

public boolean Helper(TreeNode left, TreeNode right) {

return Helper(left.left, right.right) && Helper(left.right, right.left);
}
}

 

【比大小模板】
题:270. Closest Binary Search Tree Value 二叉搜索树中,距离目标值最近的节点

private int closest(TreeNode node, double target, int val) {

if (node.val < target) val = closest(node.right, target, val);

}

 

【长度模板】
题:687. Longest Univalue Path 687.最长单值路径

public int helper(TreeNode node, int value) {

int left = helper(node.left, node.val);
int right = helper(node.right, node.val);

return Math.max(left, right) + 1;
}

题:333. Largest BST Subtree节点数最多的bst子树

public int countNode(TreeNode root) {

return 1 + countNode(root.left) + countNode(root.right);
}

 

【具体路径模板】

public void findBT(TreeNode root, String path, List<String> ans) {
ans.add(path);

findBT(root.left...);
findBT(root.right...);
}

【判断BST模板】
题:333. Largest BST Subtree节点数最多的bst子树

public boolean isValid(TreeNode root, Integer min, Integer max) {
if (root == null) return true;
if (min != null && min >= root.val) return false;
if (max != null && max <= root.val) return false;
return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}

 

这篇关于binary tree解题模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!