树总结

二叉树相关题目，用递归法最核心的思路是明确当前节点需要做的事情是什么

二叉树三种遍历

前序：根 --> 左节点 --> 右节点

中序：左节点 --> 根 --> 右节点

后序：左节点 --> 右节点 --> 根

其实顺序根、右、左在逻辑上和前序是一样的，只是定义不同

同理右、左、根在逻辑上和后序一样

调试方法

在树节点定义中加入属性order，表示节点的序号，用于debug时定位树的遍历位置

def __init__(self, val=0, order=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
    self.order = order	#节点序号

1、BST二叉搜索树

代码框架

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