本文共 2283 字，大约阅读时间需要 7 分钟。

1. 框架

二叉树是最容易培养框架思维的，大部分的常考算法本质上都是二叉树的遍历问题。废话不多说，框架如下：

class TreeNode{	int val;	TreeNode left, right;}void Traverse(TreeNode root){    Traverse(root.left);    Traverse(root.right);    // 构造成 前序、中序和后序遍历}

这类问题的总思路：先明确第一个结点需要做什么事，然后剩下的事全交给递归完成。

例1：给一棵二叉树的所有节点全部加1

void PlusOne(TreeNode root){    if(!root)        return;    root.val += 1;       // 先让根节点先加1    PlusOne(root.left);    // 递归实现后面的节点加1    PlusOne(root.right);}

例2：判断两棵二叉树是否完全相同

bool IsTheSameTree(TreeNode root1,TreeNode root2){    if(!root1 || !root2)  return false;    if(!root1 && !root2)  return true;    if(root1.val != root2.val)  return false;    // 根节点自己先做表率，告诉下面兄弟们应该怎么做，然后兄弟们照样子学就行了                                                     // 所以根节点一定要保证正确，不然后面的兄弟们都会出错了。        return IsTheSameTree(root1.left, root2.left) && IsTheSameTree(root1.right, root2.right);}

好的，热身结束。

2. 实例

1. 下面开始看剑指offer第27题：二叉树的镜像

分析：一看就知道是这个框架😄，因为对于一个节点来说，都需要交换它的左右子树。所以，对于根节点，我们需要告诉他，让他先把自己的左右子树给换个位置，然后再让下面的兄弟们也这么做（递归即可）。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */TreeNode* RevertTree(TreeNode* root){    if(!root)   return nullptr;    TreeNode* tmp = root -> left;    root -> left = root -> right;    root -> right = tmp;            // 根节点做了表率，先判断自己是不是空的，若不是，则交换自己的左右节点，若是，则返回空指针        RevertTree(root -> left);        // 所有子树开始跟根节点老大学习，都开始判断，然后看是否交换自己的左右子树。    RevertTree(root -> right);    return root;}

看，是不是很简单，再看一题。

2. 剑指offer第55题：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

int DepthOfTree(TreeNode* root){    if(!root)  return 0;    return max(DepthOfTree(root -> left), DepthOfTree(root -> right)) + 1;}

这题就三行代码?Wow!根节点在这里需要做的就是提供一个终止条件，判断自己是否到了终点，若到了，就返回0。然后dfs，往下面找最深的路径，最后加上根节点即得到答案。再看最后一题，

3. 剑指offer第54题：求二叉搜索树的第k大节点。

分析：二叉搜索树最重要的特性：通过中序遍历之后，得到的序列就是一个递增序列。

TreeNode* FindKthNode(TreeNode* root, int k){     dfs(root, k);     return root; }int count = 0;int ans = 0;void dfs(TreeNode* root, int k){    if(!root) return;    dfs(root -> right, k);    // 要往右子树去递归查找，右子树的比左子树大。    if(count == k){             // 看是否 在右子树中找到，若没有的话，那就需要去左子树找。        ans = root -> val;    return;}    dfs(root -> left, k);        }

此框架可以解决的二叉树的问题还有很多，不一一列举，单纯给读者一个思路，希望有用。

labuladong的算法小抄

转载地址：http://lmwki.baihongyu.com/