如何理解二叉树与递归的关系

二叉树一般都是和递归有联系的，二叉树的遍历包括了前序，后序，中序，大部分题目只要考虑清楚应该用那种遍历顺序，然后特殊情况的条件，题目就会迎刃而解。

1. 先来说说二叉树的遍历方式

其实二叉树的遍历很简单，无论是前，后，中序都只需要记住三个步骤

• 递归的参数和返回值
• 递归终止条件
• 递归单层逻辑

1. 1前序遍历（根左右）

// 不需要返回值，遍历当前树就可以
void preOrder(TreeNode* root) {if(root == nullptr) return;		// 终止条件// 单层逻辑cout << root->val;				// 根preOrder(root->left);			// 左preOrder(root->right);			// 右
}

1.2 后序遍历（左右根）

// 不需要返回值，遍历当前树就可以
void postOrder(TreeNode* root) {if(root == nullptr) return;		// 终止条件// 单层逻辑postOrder(root->left);			// 左cout << root->val;				// 根postOrder(root->right);			// 右
}

1.3 中序遍历（左根右）

// 不需要返回值，遍历当前树就可以
void postOrder(TreeNode* root) {if(root == nullptr) return;		// 终止条件// 单层逻辑postOrder(root->left);			// 左cout << root->val;				// 根postOrder(root->right);			// 右
}

2. 上题目

2.1 对称二叉树 Leetcode

• 分析，什么是对称二叉树？左子树==右子树就是对称。
• 返回值和参数。因为要比较左右两棵树，因此参数(TreeNode* left_tree, TreeNode* right_tree)；这里需要比较左右子树，判断是否相等，因此返回值bool

bool isLeftEqualRight(TreeNode* left_tree, TreeNode* right_tree)

• 终止条件。也是处理特殊情况

 if(left_tree == nullptr && right_tree == nullptr) return true;if(left_tree == nullptr && right_tree != nullptr) return false;if(left_tree != nullptr && right_tree == nullptr) return false;

• 单层逻辑。想象成一个有三个节点（左中右）的二叉树，此时应该如何处理。在这里就要考虑遍历顺序的问题了。是先处理根节点还是后处理根节点。这里明显是先处理根节点。

if(left_tree->val != right_tree->val) return false;
bool b1 = dfs(left_tree->left, right_tree->right);
bool b2 = dfs(left_tree->right, right_tree->left);return b1 && b2;

• 整体代码

bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return isLeftEqualRight(root->left, root->right);
}bool isLeftEqualRight(TreeNode* left_tree, TreeNode* right_tree) {// 终止条件if(left_tree == nullptr && right_tree == nullptr) return true;if(left_tree == nullptr && right_tree != nullptr) return false;if(left_tree != nullptr && right_tree == nullptr) return false;// 单层逻辑if(left_tree->val != right_tree->val) return false;bool b1 = dfs(left_tree->left, right_tree->right);bool b2 = dfs(left_tree->right, right_tree->left);return b1 && b2;
}

2.2 另一棵树的子树 Leetcode

• 分析。子树如果在另一棵树出现过，说明另一棵树存在一棵树完全和子树相同，我们就只需要看是否有完全相同的树就可以
• 返回值和参数。求是否包含，需要由左右子树的状态共同决定，返回值bool。求子树是否在另一棵树出现过，两个参数(TreeNode* root, TreeNode* subTree)
• 终止条件。特殊情况

if(root == nullptr) return false;

• 单层逻辑。当前树是否和子树完全相同，如果相同，返回true；否则看左右子树的情况

if(isSameTree(root, subRoot)) return true;//看左右子树，是否相等
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);

这里需要求两棵树是否完全一样isSameTree(TreeNode* p, TreeNode* q)

bool isSameTree(TreeNode* p, TreeNode* q) {if(p == nullptr && q == nullptr) return true;if(p == nullptr && q != nullptr) return false;if(p != nullptr && q == nullptr) return false;if(p->val != q->val) return false;bool b1 = isSameTree(p->left, q->left);bool b2 = isSameTree(p->right, q->right);return b1 && b2;
}

• 完整代码

//subRoot是root的子树，root中一定有一个树结构和subRoot相等
bool isSubtree(TreeNode* root, TreeNode* subRoot) 
{//终止条件if(root == nullptr) return false;if(isSameTree(root, subRoot)) return true;//看左右子树，是否相等return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}bool isSameTree(TreeNode* p, TreeNode* q)
{if(p == nullptr && q == nullptr) return true;else if(p == nullptr && q != nullptr) return false;else if(p != nullptr && q == nullptr) return false;else if(p->val != q->val) return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

2.3 二叉树的最大深度 Leetcode

• 分析，二叉树的最大深度？max(左子树深度, 右子树深度) + 1
• 返回值和参数。求当前树，只需要当前树就可以，参数(TreeNode* root)；求深度，返回值int

int maxDepth(TreeNode* root)

• 终止条件。特殊条件

if(root == nullptr) return 0;

• 单层逻辑。确定遍历顺序。因为当前树的情况依赖与左右子树的情况，因此需要先遍历左右，再处理根节点，显然后续。

int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);return max(left_depth, right_depth) + 1;

• 完整代码

int maxDepth(TreeNode* root) {// 终止条件if(root == nullptr) return 0;// 单层逻辑int left_depth = maxDepth(root->left);int right_depth = maxDepth(root->right);return max(left_depth, right_depth) + 1;}

2.4 二叉树的最小深度 Leetcode

• 分析，最小深度？左右子树深度的最小值确定当前当前树的最小深度。但是如果左子树为空，那最小深度一定由右子树确定。反之类似。
• 返回值和参数。求当前树，只需要当前树就可以，参数(TreeNode* root)；求深度，返回值int
• 终止条件。特殊情况

if(root == nullptr) return 0;

• 单层逻辑。想象有三个节点（左中右）的树，当前树的最小深度由左右子树共同确定，因此是后序遍历。这里需要注意，如果左子树为空，那最小深度就是右子树。反之类似。

int left_depth = minDepth(root->left);
int right_depth = minDepth(root->right);// 左子树为nullptr，由右子树确定
if(root->left == nullptr) return right_depth + 1;
if(root->right == nullptr) return left_depth + 1;return min(left_depth, right_depth) + 1;

• 完整代码

int minDepth(TreeNode* root) {// 终止条件if(root == nullptr) return 0;// 单层逻辑int left_depth = minDepth(root->left);int right_depth = minDepth(root->right);if(root->left == nullptr) return right_depth + 1;if(root->right == nullptr) return left_depth + 1;return min(left_depth, right_depth) + 1;
}

2.5 平衡二叉树 Leetcode

• 分析。什么是平衡二叉树？左子树高度-右子树高度 <= 1，因此我们要求左右子树的高度，然后比较两者差值
• 返回值和参数。求当前树，只需要当前树就可以，参数(TreeNode* root)；求高度，返回值int
• 终止条件。特殊情况

if(root == nullptr) return 0;

• 单层逻辑。判断左右子树的高度差，>1，返回-1表示不是平衡的，当正常返回高度，就是平衡的。这里其实设计到剪枝操作，每次不满足条件了，我们应该提前返回。

int left_height = getHeight(root->left);
if(left_height == -1) return -1;
int right_height = getHeight(root->right);
if(right_height == -1) return -1;if(abs(left_height-right_height) > 1) return -1;
else return max(left_height, right_height) + 1;

• 完整代码

bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}// 左右高度差 <= 1
int getHeight(TreeNode* root) {if(root == nullptr) return 0;int left_height = getHeight(root->left);if(left_height == -1) return -1;int right_height = getHeight(root->right);if(right_height == -1) return -1;if(abs(left_height-right_height) > 1) return -1;else return max(left_height, right_height) + 1;
}

2.6 完全二叉树的节点个数 Leetcode

• 分析。完全二叉树是由满二叉树构成，如果当前是满二叉树（左右子树高度一样），那直接就(2 << n) - 1，然后再计算左右子树的节点数量，最后确定当前树的节点数量
• 返回值和参数。求当前树，只需要当前树就可以，参数(TreeNode* root)；求节点个数，返回值int

int countNodes(TreeNode* root)

• 终止条件。特殊情况

if(root == nullptr) return 0;

• 单层逻辑。当前是树是满二叉树（左右子树高度一样），直接算(2 << n) - 1。否则求左右子树节点数量。

TreeNode* left_tree = root->left;
TreeNode* right_tree = root->right;
int left_height = 0;
int right_height = 0;while(left_tree) {left_height++;left_tree = left_tree->left;
}while(right_tree) {right_height++;right_tree = right_tree->right;
}if(left_height == right_height) {return (2<<left_height) - 1;
}int c1 = countNodes(root->left);
int c2 = countNodes(root->right);return c1 + c2 + 1;

• 完整代码

 int countNodes(TreeNode* root) {if(root == nullptr) return 0;// 当前是不是满二叉树(左子树高度和右子树高度一样)TreeNode* left_tree = root->left;TreeNode* right_tree = root->right;int left_height = 0;int right_height = 0;while(left_tree){left_height++;left_tree = left_tree->left;}while(right_tree){right_height++;right_tree = right_tree->right;}if(left_height == right_height){return (2<<left_height) - 1;}int c1 = countNodes(root->left);int c2 = countNodes(root->right);return c1 + c2 + 1;
}

2.7 二叉树的所有路径 Leetcode

• 分析。路径：每次从根节点遍历到叶子节点root->left == nullptr && root->right == nullptr时，就是一条完整的路径，应该记录来。
• 返回值与参数。因为每次递归涉及到当前节点和路径，因此参数(TreeNode* root, string path)。这里我们虽然要求所有的路径，但是这是整棵树情况，相当于是遍历整棵树，并不需要左右子树的结果才能推出当前树的结果（平衡，最大最小深度，节点个数都需要左右子树的状态才能确定当前树的状态），所以返回值void。这里需要注意，我们需要一个全局遍历，存最后的结果vector<string> res
• 终止条件。特殊情况

if(root == nullptr) return;

• 单层逻辑。当遍历到当前节点并且满足是叶子节点时，说明path记录了完整路径，需要被记录。否则就需要继续处理左右子树。

if(root == nullptr) return;// 每次进来先把当前节点的值加入到路径
path += to_string(root->val);if(root->left == nullptr && root->right == nullptr)
{res.push_back(path);
}//这里已经回溯过了
dfs(root->left, path + "->");
dfs(root->right, path + "->");

• 完整代码

vector<string> res;vector<string> binaryTreePaths(TreeNode* root) 
{if(root == nullptr) return res;string path = "";dfs(root,  path);return res;
}void dfs(TreeNode* root, string path)
{if(root == nullptr) return;path += to_string(root->val);if(root->left == nullptr && root->right == nullptr){res.push_back(path);}//这里已经回溯过了dfs(root->left, path + "->");dfs(root->right, path + "->");
}

2.8 路径总和 Leetcode

• 分析。路径：每次从根节点遍历到叶子节点root->left == nullptr && root->right == nullptr时，就是一条完整的路径，此时需要看targetNum是否刚好==0，刚好等于0说明这条路径上的和就是targetNum
• 返回值和参数。是否满足条件，并且当前树的情况和左右子树的状态都有关系，返回值bool。参数，当前树，有无满足路径和为targetNum的，因此需要两个参数(TreeNode* root, int targetNum)。
• 终止条件。特殊情况

if(root == nullptr) return false;

• 单层逻辑。如果当前节点是叶子节点，说明已经找到一条路径，判断targetNum是否是0，是就返回true；否则还需要看左右子树的状态

// 先记录当前值
targetSum -= root->val;
if(root->left == nullptr && root->right == nullptr)
{if(targetSum == 0){return true;}
}bool b1 = hasPathSum(root->left, targetSum);
if(b1) return true;bool b2 = hasPathSum(root->right, targetSum);        
if(b2) return true;return false;

• 完整代码

bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return false;targetSum -= root->val;
if(root->left == nullptr && root->right == nullptr)
{if(targetSum == 0){return true;}
}bool b1 = hasPathSum(root->left, targetSum);
if(b1) return true;	// 一个剪枝操作bool b2 = hasPathSum(root->right, targetSum);        
if(b2) return true;return false;
}

2.9 左叶子之和 Leetcode

• 分析。什么是左叶子？root->left && root->left->left == nullptr && root->left->right == nullptr说明root->left就是左叶子
• 返回值和参数。求做左叶子之和，当前节点依赖于左右子树的状态，返回值int。求当前树，参数(TreeNode* root)
• 终止条件。特殊情况

if(root == nullptr) return 0;

• 单层逻辑。找当前节点的左叶子，然后再找左右子树的做叶子之和。

// 当前节点的左叶子节点
int curValue = 0;
if(root->left && root->left->left == nullptr && root->left->right == nullptr) 
{   curValue = root->left->val;
}int s1 = sumOfLeftLeaves(root->left);
int s2 = sumOfLeftLeaves(root->right);return s1 + s2 + curValue;

• 完整代码

int sumOfLeftLeaves(TreeNode* root) {if(root == nullptr) return 0;
// 当前节点的左叶子节点
int curValue = 0;
if(root->left && root->left->left == nullptr && root->left->right == nullptr) 
{   curValue = root->left->val;
}int s1 = sumOfLeftLeaves(root->left);
int s2 = sumOfLeftLeaves(root->right);return s1 + s2 + curValue;}

2.10 找树左下角的值 Leetcode

• 分析。左下角的值？最深的一层的第一个节点。因此需要一个变量记录树当前的最大深度max_depth
• 返回值与参数。找最左下角的值，但是当前树最左下的值和左右子树的状态没有关系，返回值void。要判断当前节点的深度是不是最大深度，因此有两个参数(TreeNode* root, int depth)
• 终止条件。特殊情况

if(root == nullptr) return;

• 单层逻辑。遍历到叶子节点时，如果该叶子节点所在深度大于max_depth，说明该叶子节点是当前层的第一个节点（左叶子节点）。没找到，就继续在左右子树找

if(root->left == nullptr && root->right == nullptr)
{if(depth > max_depth) {res = root->val;max_depth = depth;}
}dfs(root->left, depth+1);
dfs(root->right, depth+1);

• 完整代码

int max_depth = INT_MIN;
int res = 0;
int findBottomLeftValue(TreeNode* root) {if(root == nullptr) return 0;dfs(root, 1);return res;
}void dfs(TreeNode* root, int depth)
{if(root == nullptr) return;if(root->left == nullptr && root->right == nullptr){if(depth > max_depth) {res = root->val;max_depth = depth;}}dfs(root->left, depth+1);dfs(root->right, depth+1);
}

3. 二叉树的修改与构造

3.1 翻转二叉树 Leetcode

• 分析。要想翻转一棵二叉树，先翻转左右子树，先翻转当前节点左右子树，明显是后序
• 返回值和参数。要求翻转后的二叉树，并且当前树的状态和左右子树有关系，因此返回值TreeNode*。求当前树，参数(TreeNode* root)
• 终止条件。特殊情况

if(root == nullptr) return nullptr;

• 单层逻辑。先翻转左右子树，先翻转当前节点左右子树。

TreeNode* left_tree = invertTree(root->left);
TreeNode* right_tree = invertTree(root->right);root->left = right_tree;
root->right = left_tree;return root;

• 完整代码

TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) return nullptr;TreeNode* left_tree = invertTree(root->left);
TreeNode* right_tree = invertTree(root->right);root->left = right_tree;
root->right = left_tree;return root;
}

3.2 从中序与后序遍历序列构造二叉树 Leetcode

• 分析。后序：左右中；中序：左中右。我们可以在后序中找到中间节点（最后一个），然后再根据该节点划分中序，分成左，中，右三个部分，然后就可以递归处理左，右。
• 返回值和参数。要求构造的二叉树，当前树和左右子树的状态有关系，返回值TreeNode*。我们每次要确定中序和后序的左右边界，一个好的想法是直接在参数中表明，因此参数(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd)。
• 终止条件。特殊情况

if(inStart >= inEnd) return nullptr;

• 单层逻辑。先在后序找到中节点，再根据中节点将中序划分为左，中，右，最后递归处理左，右子树

//在前序找中
int mid_val = postorder[postEnd - 1];
TreeNode* root = new TreeNode(mid_val);//在中序找中
int mid_idx = 0;
for(int i = inStart; i<inEnd; ++i)
{if(inorder[i] == mid_val){mid_idx = i;break;}
}//左子树
int inLeftStart = inStart;
int inLeftEnd = mid_idx;
int postLeftStart = postStart;
int postLeftEnd = postStart + mid_idx - inStart;
TreeNode* left_tree = dfs(inorder, inLeftStart, inLeftEnd, postorder, postLeftStart, postLeftEnd);//右子树
int inRightStart = inLeftEnd + 1;
int inRightEnd = inEnd;
int postRightStart = postLeftEnd;
int postRightEnd = postEnd - 1;
TreeNode* right_tree = dfs(inorder, inRightStart, inRightEnd, postorder, postRightStart, postRightEnd);root->left = left_tree;
root->right = right_tree;return root;

• 完整代码

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return dfs(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}TreeNode* dfs(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd)
{if(inStart >= inEnd) return nullptr;//在前序找中int mid_val = postorder[postEnd - 1];TreeNode* root = new TreeNode(mid_val);//在中序找中int mid_idx = 0;for(int i = inStart; i<inEnd; ++i){if(inorder[i] == mid_val){mid_idx = i;break;}}//左子树int inLeftStart = inStart;int inLeftEnd = mid_idx;int postLeftStart = postStart;int postLeftEnd = postStart + mid_idx - inStart;TreeNode* left_tree = dfs(inorder, inLeftStart, inLeftEnd, postorder, postLeftStart, postLeftEnd);//右子树int inRightStart = inLeftEnd + 1;int inRightEnd = inEnd;int postRightStart = postLeftEnd;int postRightEnd = postEnd - 1;TreeNode* right_tree = dfs(inorder, inRightStart, inRightEnd, postorder, postRightStart, postRightEnd);root->left = left_tree;root->right = right_tree;return root;
}

3.3 最大二叉树 Leetcode

• 分析。先找到最大值，再划分左右子树，递归处理左右子树
• 返回值和参数。求构造的最大二叉树，并且当前树依赖于左右节点状态，返回值TreeNode*。确定当前处理的区间，参数·(vector<int>& nums, int start, int end)
• 终止条件。特殊情况

if(start >= end) return nullptr;

• 单层逻辑。先找到最大值，再划分左右子树，递归处理左右子树

//找到最大值
int max_val = INT_MIN;
int max_idx = -1;
for(int i = start; i<end; ++i)
{if(nums[i] > max_val){max_val = nums[i];max_idx = i;}
}TreeNode* root = new TreeNode(max_val);//左
int leftStart = start;
int leftEnd = max_idx;
TreeNode* left_tree = dfs(nums, leftStart, leftEnd);
//右
int rightStart = leftEnd + 1;
int rightEnd = end;
TreeNode* right_tree = dfs(nums, rightStart, rightEnd);root->left = left_tree;
root->right = right_tree;return root;        

3.4 合并二叉树 Leetcode

• 分析。如果两棵树都不是null，把root2合并到root1上。先处理当前节点，然后处理左右子树。
• 返回值和参数。求合并后的二叉树，并且当前树和左右子树的状态有关系，因此返回值TreeNode*。合并两个数，参数(TreeNode* root1, TreeNode* root2)
• 终止条件。当任意一棵树为null，返回另一棵树

if(root1 == nullptr) return root2;
if(root2 == nullptr) return root1;

• 单层逻辑。如果两棵树都不是null，把root2合并到root1上。先处理当前节点，然后处理左右子树。

root1->val = root1->val + root2->val;TreeNode* left_tree = mergeTrees(root1->left, root2->left);
TreeNode* right_tree = mergeTrees(root1->right, root2->right);root1->left = left_tree;
root1->right = right_tree;return root1;

• 完整代码

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr) return root2;if(root2 == nullptr) return root1;root1->val = root1->val + root2->val;TreeNode* left_tree = mergeTrees(root1->left, root2->left);TreeNode* right_tree = mergeTrees(root1->right, root2->right);root1->left = left_tree;root1->right = right_tree;return root1;
}