关于树的基本题目

关于树的基本题目

天下谁人不识“树”？

树是一个常见的结构，一般人还真不好说出来详尽的解释与介绍，比如常见的红黑树，再扩展一下，树模型有没有用过，比如gbdt与xgboost有什么区别与联系？怎么训练的（分叉的）？输入样本是什么？

夺命三连，招招致命。

1-三种遍历方式

前中后，先建立个树结构，

public static class TreeNode {
	public int value;
	public TreeNode left;
	public TreeNode right;

	public TreeNode(int data) {
		this.value = data;
	}
}

递归方式实现，如下：

// 前
public static void preOrder(TreeNode head) {
	if (head == null) {
		return;
	}
	System.out.print(head.value + " ");
	preOrder(head.left);
	preOrder(head.right);
}

// 中
public static void inOrder(TreeNode head) {
	if (head == null) {
		return;
	}
	inOrder(head.left);
	System.out.print(head.value + " ");
	inOrder(head.right);
}

// 后
public static void posOrder(TreeNode head) {
	if (head == null) {
		return;
	}
	posOrder(head.left);
	posOrder(head.right);
	System.out.print(head.value + " ");
}

注意java的main函数写在类里面，上述函数均在内。

public static void main(String[] args)

2-判断是否为平衡二叉树

平衡二叉树的性质（概念）：空树或者左右子树的高度差不超过1.

判断方式：要么左子树不是平衡二叉树，要么右子树不是平衡二叉树，要么整个不是平衡二叉树。

关键要素：左子树和右子树高度差不超过 1。（任何节点的树都要满足这个）【下面的来源于网页搜索结果，看起来比较复杂，其实不应该这么难的】

public class BtreeNode {
    public int value;
    public BtreeNode left;
    public BtreeNode right;

    public BtreeNode(int value) {
        this.value = value;
    }

    public static boolean isBalanced(BtreeNode head) {
        return process(head).isBalanced;
    }

    public static class ReturnType {
        public boolean isBalanced;
        public int height;

        public ReturnType(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static ReturnType process(BtreeNode head) {
        if (head == null) {
            return new ReturnType(true, 0);
        }
        ReturnType leftData = process(head.left);
        ReturnType rightData = process(head.right);
        int height = Math.max(leftData.height, rightData.height) + 1;
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;
        return new ReturnType(isBalanced, height);
    }

}

因此本大佬又搜了个简单的，相当简单。如下：一般来说无需写树结构

    public boolean result=true;
    public static boolean isBalanced(BtreeNode2 root) {
        if(root==null)return true;
        if(Math.abs(depth(root.left)-depth(root.right))>1)return false;
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public static int depth(BtreeNode2 root){
        if(root==null)return 0;
        return Math.max(depth(root.left),depth(root.right))+1;
    }

3-最大搜索二叉子树（最大查找树）

首先明确一个概念，二叉搜索树（二叉查找树，二叉排序树）是指的是左子树所有节点的值均小于根节点的值，右子树所有节点的值均大于根节点的值，要么就是空树。

一个无序的树中，寻找最大的有序的树。

判断方法：左子树最大值<当前结点值<右子树最小值 && 左子树中的二叉搜索树根是左儿子 && 右子树中的二叉搜索树根是是右儿子。

这个java版本实在是太过于繁琐了，因此还是用py版本的吧，源于网页搜索结果。

class Solution:
    def largestBSTSubtree(self, root):
        self.maxSize = 0
        self.maxRoot = None
        def helper(root):
          # 返回一个元组 (size, minValue, maxValue) 表示当前结点对应子树的信息.
            if root is None:
                return (0, float('inf'), float('-inf'))
            left = helper(root.left)
            right = helper(root.right)
            if root.value > left[2] and root.value < right[1]:
                size = left[0] + right[0] + 1
                if size > self.maxSize:
                    self.maxSize = size
                    self.maxRoot = root
                return (size, min(root.value, left[1]), max(root.value, right[2]))
            else:
                return (0, float('-inf'), float('inf'))
        helper(root)
        return self.maxRoot

愿我们终有重逢之时，而你还记得我们曾经讨论的话题。