二叉树专题

说点废话

看到今天的力扣的每日一题是一道跟二叉树有关的，递归题目，突然发现自己对树的相关知识有点忘得一干二净了，于是就想复习一下，于是就有了这篇文章。

什么事二叉树

一种数据结构。当然其实我写这篇文章并不想讲这些基础概念什么balabala的，我只是想复习和二叉树有关的算法（逃，所以我选择贴链接：维基百科——二叉树
给出最基本的树的结点的代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

public class TreeNode 
{
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) 
	{
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

二叉树的各种操作

遍历

对一棵二叉树进行遍历，其实就是用DFS和BFS，而DFS又有三种顺序：前序、中序、后序。前序就是中左右，中序就是左中右，后序就是左右中。BFS的话就是按层次从左到右了。
根据上面对树结点的定义和遍历思路，我们可以很快写出代码：

def preOrder(node: TreeNode):
    print(node.val)
    if node.left is not None:
        preOrder(node.left)
    if node.right is not None:
        preOrder(node.right)

public class TreeMethods 
{
	public void PreOrder(TreeNode node) 
	{
		Console.WriteLine(node.val);
		if (node.left != null)
		{
			PreOrder(node.left);
		}
		if (node.right != null)
		{
			PreOrder(node.right);
		}
	}
}

只有前序遍历是因为另外两个照葫芦画瓢就好了。
下面是用BFS按层次遍历的代码：

def preOrderBFS(node: TreeNode):
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        print(cur.val)
        if cur.left is not None:
            preOrderBFS(cur.left)
        if cur.right is not None:
            preOrderBFS(cur.right)

public void PreOrderBFS(TreeNode node)
{
	Queue<TreeNode> queue = new Queue<TreeNode>();
	queue.Enqueue(node);
	while (queue.Any())
	{
		TreeNode cur = queue.Dequeue();
		Console.WriteLine(cur.val);
		if (cur.left != null)
		{
			queue.Enqueue(cur.left);
		}
		if (cur.right != null)
		{
			queue.Enqueue(cur.right);
		}
	}
}

二叉树的深度

思想：遍历，往下递的过程是走完左子树和右子树，往上归的过程是传递当前最深深度。

def depth(node: TreeNode):
    if node is None:
        return 0
    if node.left is not None:
        leftDepth = depth(node.left)
    else:
        leftDepth = 0
    if node.right is not None:
        rightDepth = depth(node.right)
    else:
        rightDepth = 0
    return leftDepth + 1 if leftDepth > rightDepth else rightDepth + 1

public int Depth(TreeNode node)
{
	int leftDepth = 0, rightDepth = 0;
	if (node == null)
	{
		return 0;
	}
	if (node.left != null)
	{
		leftDepth = Depth(node.left);
	}
	else
	{
		leftDepth = 0;
	}
	if (node.right != null)
	{
		rightDepth = Depth(node.right);
	}
	else
	{
		rightDepth = 0;
	}
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

ok，其实到目前为止今天遇到的那道题的知识已经够了，现在来看看题目吧。

题目描述

1080. 根到叶路径上的不足节点

思路及实现

明确不足节点的概念，哪些节点应该删除，哪些不能。假如现在有一个叶子节点，它的“根-叶”路径上值的总和全都小于给定的limit，那么这个叶子节点就是不足节点，我们可以删除它。
那假如现在有一个非叶子节点，要怎么知道它能不能够删除呢？那就要看它是否还有儿子。如果这个非叶子节点的儿子都被删除了，说明它的儿子都是不足节点（仔细读题（说实话，题目描述有点垃圾了），只要是通过这个非叶子节点node的每种可能的“根-叶”路径上值的总和全都小于给定的limit，那么这个非叶子节点就是不足节点），也就说明当前这个非叶子节点每种可能的“根-叶”路径上值的总和小于limit了，那么就需要删除它。如果它存在一个儿子不是不足节点，那我们就不能够删除它。

如果还是不理解的话，简单来说，非叶子节点node的儿子都被删除的话，那它也需要删除；如果非叶子节点存在儿子未被删除，那它就不能删除。

那么就可以利用递归，往下传递的就是当前路径值，往回归的就是自身或者是null（判断为不足节点，被删除了，所以返回null）。

class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        # 计算当前路径和
        limit -= root.val
        if root.left is None and root.right is None:  # 当前节点为叶子节点
            return root if limit <= 0 else None  # 判断是否为不足节点
        if root.left:
            root.left = self.sufficientSubset(root.left, limit)  # 把值传递下去，判断这条路是否满足条件
        if root.right:
            root.right = self.sufficientSubset(root.right, limit)
        return root if root.left or root.right else None  # 如果非叶子节点的儿子都被删除了，它也应该被删除

另外看到一个思路略微不同但是写得很佬的题解：Broncos的题解

关于本篇

以后还会更新

---

希望本文章能够帮到您~