二叉树算法解析

二叉树的问题的解决办法主要采用递归的方法解决

主要有两种：

递归遍历

递归分治

90%的问题可以采用递归分治的办法解决。

1.递归遍历的方法

定义一个全局变量，将该变量作为一个结果参数传入一个定义的空返回值类型的辅助函数。

递归遍历的方法，是一种不断得递归深入遍历，亲力亲为。遍历的顺序很重要。

2.递归分治的方法

分治的办法通常可以不用定义辅助函数，或者定义一个有返回结果的辅助。分治递归左右子树的顺序不重要

分治的方法，是将该任务分配左右子节点。

分治法，关键是怎样利用左右子树的结果，即假设已经获得左右子树的结果，怎样利用左右子树的结果获得全局的结果。

思考一个关系：左右子树的结果和整棵树的结果的关系是什么?

递归的边界条件：首先考虑，root为空的情况

再考虑叶子节点的方法

1.前序遍历的三种写法

private static class TreeNode {

int val;

TreeNode left;

TreeNode right;

public TreeNode(int val) {

this.val = val;

left = null;

right = null;

}

}

public List<Integer> preorderTraversal_1(TreeNode root) {

List<Integer> result = new ArrayList<Integer>();

if (root == null) {

return result;

}

Stack<TreeNode> stack = new Stack<TreeNode>();

stack.push(root);

while(!stack.isEmpty()) {

TreeNode node = stack.pop();

result.add(node.val);

if (node.right != null) {

stack.push(node.right);

}

if (node.left != null) {

stack.push(node.left);

}

}

return result;

}

public List<Integer> preorderTraversal_2(TreeNode root) {

List<Integer> result = new ArrayList<Integer>();

preorderCore(root, result);

return result;

}

public void preorderCore(TreeNode root, List<Integer> result) {

if (root == null) {

return ;

}

result.add(root.val);

if (root.left != null) {

preorderCore(root.left, result);

}

if (root.right != null) {

preorderCore(root.right,result);

}

}

public List<Integer> preorderTraversal_3(TreeNode root) {

List<Integer> result = new ArrayList<Integer>();

if (root == null) {

return result;

}

List<Integer> left = preorderTraversal_3(root.left);

List<Integer> right = preorderTraversal_3(root.right);

result.add(root.val);

result.addAll(left);

result.addAll(right);

return result;

}

2.求树的最大深度

public class Solution1 {

public int maxDepth(TreeNode root) {

if (root == null) {

return 0;

}

int left = maxDepth(root.left);

int right = maxDepth(root.right);

return left > right ? (left + 1) :(right + 1);

}

}

public class Solution_1 {

private int depth;

public int maxDepth1(TreeNode root) {

depth = 0;

helper (root, 1);

return depth;

}

private void helper(TreeNode root, int curDepth) {

if (root == null) {

return ;

}

if (curDepth > depth) {

depth = curDepth;

}

helper(root.left, curDepth + 1);

helper(root.right, curDepth + 1);

}

}

3.求二叉树的所有路径

public class Solution2 {

public List<String> binaryTreePaths(TreeNode root) {

List<String> result = new ArrayList<String>();

if (root == null) {

return result;

}

if (root.left == null && root.right == null) {

result.add("" + root.val);

}

List<String> left = binaryTreePaths(root.left);

List<String> right = binaryTreePaths(root.right);

for (String path : left) {

result.add(root.val + "->" + path);

}

for (String path : right) {

result.add(root.val + "->" +path);

}

return result;

}

}

public class Soulution_2 {

public List<String> binaryTreePaths(TreeNode root) {

List<String> result = new ArrayList<String>();

if (root == null) {

return result;

}

helper (root, String.valueOf(root.val), result);

return result;

}

private void helper(TreeNode root, String path, List<String> result) {

if (root == null) {

return ;

}

if (root.left == null && root.right ==null) {

result.add(path);

}

if (root.left != null) {

helper(root.left, path + "->" + String.valueOf(root.left.val), result);

}

if (root.right != null) {

helper(root.right, path + "->" + String.valueOf(root.right.val), result);

}

}

}

4.求出最小和子树

public class Solution3 {

private int curSum = Integer.MAX_VALUE;

private TreeNode sub = null;

public TreeNode findSubtree(TreeNode root) {

helper(root);

return sub;

}

private int helper(TreeNode root) {

if (root == null) {

return 0;

}

int sum = root.val + helper(root.left) + helper(root.right);

if (sum <= curSum) {

curSum = sum;

sub = root;

}

return sum;

}

}

public class Solution {

private class resultType {

public TreeNode sub;

public int minSum;

public int sum;

public resultType(TreeNode sub, int minSum, int sum) {

this.sub = sub;

this.minSum = minSum;

this.sum = sum;

}

}

public TreeNode findSubtree(TreeNode root) {

resultType result = helper(root);

return result.sub;

}

private resultType helper(TreeNode root) {

if (root == null) {

return new resultType(null, Integer.MAX_VALUE, 0);

}

resultType left = helper(root.left);

resultType right = helper(root.right);

resultType result = new resultType(

root,

root.val + left.sum + right.sum,

root.val + left.sum + right.sum

);

if (left.minSum <= result.minSum) {

result.sub = left.sub;

result.minSum = left.minSum;

}

if (right.minSum <= result.minSum) {

result.sub = right.sub;

result.minSum = right.minSum;

}

return result;

}

}

4. 当用分治的方法写辅助函数需要返回两个值的时候，可以重新定义结果类ResultType用来保存返回的结果

public class Solution4 {

private class ResultType {

private boolean isBalanced;

private int high;

public ResultType(boolean isBalanced, int high) {

this.isBalanced = isBalanced;

this.high = high;

}

}

public boolean isBalanced(TreeNode root) {

return helper(root).isBalanced;

}

private ResultType helper(TreeNode root) {

if (root == null) {

return new ResultType(true, 0);

}

ResultType left = helper(root.left);

ResultType right = helper(root.right);

if(!left.isBalanced || !right.isBalanced) {

return new ResultType(false, -1);

}

if(Math.abs(left.high - right.high) > 1) {

return new ResultType(false, -1);

}

return new ResultType(true, Math.max(left.high, right.high)+ 1);

}

}

public class Solution4_1 {

public boolean isBalanced(TreeNode root) {

return find(root) != -1;

}

public int find(TreeNode root) {

if (root == null) {

return 0;

}

int left = find( root.left );

int right = find( root.right);

if (left == -1 || right == -1 || Math.abs(left - right) > 1) {

return -1;

}

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

}

}

5. 结合ResType和分治+递归遍历结合的方式

public class Solution5 {

private class ResultType {

public int sum, size;

public ResultType(int sum, int size) {

this.sum = sum;

this.size = size;

}

}

private ResultType subtreeResult = null;

private TreeNode node = null;

public TreeNode findSubtree2(TreeNode root) {

helper(root);

return node;

}

private ResultType helper(TreeNode root) {

if (root == null) {

return new ResultType(0,0);

}

ResultType left = helper(root.left);

ResultType right = helper(root.right);

ResultType result = new ResultType(

left.sum + right.sum +root.val,

left.size + right.size +1);

if (node == null || result.sum * subtreeResult.size > subtreeResult.sum * result.size) {

subtreeResult = result;

node = root;

}

return result;

}

}

相关知识

机器学习算法
算法复杂度解析与实例
Android数据结构与算法之一 基础简介
【免费】中山大学大学生程序设计竞赛2>=
NOIP初赛知识点复习总结
RFID防碰撞算法及安全认证协议的研究
NOIP初赛知识点复习总结市公开课一等奖省赛课微课金奖课件.pptx
树的整理
花粥没有花
【机器学习】基于KNN算法实现鸢尾花数据集的分类

网址: 二叉树算法解析 https://www.huajiangbk.com/newsview1356581.html