内容主要包含： 1. 二叉树中DFS三种搜索的模板程序 （递归+非递归） 2. 二叉树BFS非递归版本 3. 二叉树常见到必背的考题 不管你是刷题学习，还是准备面试，二叉树下面的这几个程序都是 理解记忆并背诵！理解记忆并背诵！理解记忆并背诵！重要的事情说三遍

真的太常用了，小哥哥小姐姐一定要掌握哦~

BFS递归版本

void bfs(TreeNode *node, queue<TreeNode*> q) { if (q.empty()) { return; } TreeNode *node = q.front(); q.pop(); cout << node->val << endl; if (node->left) { q.push(node->left); } if (node->right) { q.push(node->right); } bfs(node, q); }

二叉树中序遍历

非递归1-最通用的版本

vector<int> inorderTraversal(TreeNode * root) { if (root == NULL) { return vector<int>(); } vector<int> ret; stack<TreeNode*> s; while (root != NULL) { s.push(root); root = root->left; } while (!s.empty()) { TreeNode *curt = s.top(); ret.push_back(curt->val); if (curt->right == NULL) { s.pop(); while (!s.empty() && s.top()->right == curt) { curt = s.top(); s.pop(); } } else { curt = curt->right; while (curt != NULL) { s.push(curt); curt = curt->left; } } } return ret; }

非递归2-常见版本

vector<int> inorderTraversal(TreeNode * root) { // 中序遍历的非递归版本 vector<int> result; stack<TreeNode*> s; TreeNode* cur = root; while(cur != NULL || !s.empty()) { while(cur != NULL) { s.push(cur); cur = cur->left; } cur = s.top(); s.pop(); result.push_back(cur->val); cur = cur->right; } return result; }

二叉树前序遍历

递归之traverse

vector<int> preorderTraversal(TreeNode * root) { vector<int> result; // 定义：以root为根节点的先序遍历结果放到result中 traverse(root, result); return result; } void traverse(TreeNode *root, vector<int> &result) { // 这个地方每次都要传地址，因为每次都要修改，相当于一个全局变量 if (root == NULL) { return; } result.push_back(root->val); traverse(root->left, result); traverse(root->right, result); }

非递归版本

vector<int> preorderTraversal(TreeNode * root) { if (root == NULL) { return vector<int>(); } vector<int> result; stack<TreeNode*> s; s.push(root); while(!s.empty()) { TreeNode *node = s.top(); s.pop(); result.push_back(node->val); if(node->right!=NULL) { s.push(node->right); } if(node->left!=NULL) { s.push(node->left); } } return result; }

二叉树后序遍历

非递归版本

vector<int> postorderTraversal(TreeNode * root) { // write your code here vector<int> result; stack<TreeNode*> s; TreeNode *current = root, *lastVisit = NULL; while(current!=NULL || !s.empty()) { while(current != NULL) { s.push(current); current = current->left; } current = s.top(); // 此时先不要急着出栈 if(current->right == NULL || current->right == lastVisit) { s.pop(); result.push_back(current->val); lastVisit = current; current = NULL; } else { current = current->right; } } return result; }

二叉树基本考题

MaxDepth of binary tree

int maxDepth(TreeNode *root) { // write your code here if(root == NULL) { return 0; } // Divide int left = maxDepth(root->left); int right = maxDepth(root->right); // Conquer return max(left, right) + 1; }

MinDepth of binary tree

int minDepth(TreeNode * root) { // write your code here if(root == NULL) { return 0; } // Divide int left = minDepth(root->left); int right = minDepth(root->right); // Conquer if(left == 0 && right == 0) { return 1; }else if(left == 0 && right != 0) { return right + 1; }else if(left != 0 && right == 0) { return left + 1; }else { return min(left, right) + 1; } }

平衡二叉树判断

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class ResultType { public: int maxDepth; bool isBalanced; public: ResultType(int maxDepth, int isBalanced) { this->maxDepth = maxDepth; this->isBalanced = isBalanced; } }; class Solution { public: /* * @param root: The root of binary tree. * @return: True if this Binary tree is Balanced, or false. */ bool isBalanced(TreeNode * root) { // write your code here return helper(root).isBalanced; } ResultType helper(TreeNode* root) { if(root == NULL) { return ResultType(0, true); } // Divide ResultType left = helper(root->left); ResultType right = helper(root->right); // Conquer if(!left.isBalanced || !right.isBalanced) { return ResultType(-1, false); } if(abs(left.maxDepth - right.maxDepth) > 1) { return ResultType(-1, false); } return ResultType(max(left.maxDepth, right.maxDepth) + 1, true); } };

二叉搜索树判断

class Solution { public: bool isValid; TreeNode *lastNode; bool isValidBST(TreeNode * root) { lastNode = NULL; isValid = true; traverse(root); return isValid; } // 利用中序遍历是升序序列的特性来做，一边遍历一遍给出结果 void traverse(TreeNode *root) { // 先处理特殊情况，或者是退出情况 if (root == NULL) { return; } traverse(root->left); // 根 if (lastNode != NULL && lastNode->val >= root->val) { isValid = false; return; } lastNode = root; traverse(root->right); } }; // 不要去记录最大值最小值，当节点为NULL的时候，不好处理。记录下最小最大的节点。不存在的话就直接给NULL就行了。 struct ResultType { bool isBST; TreeNode *maxNode; TreeNode *minNode; ResultType(bool isBST) { this->isBST = isBST; this->maxNode = NULL; this->minNode = NULL; } }; bool isValidBST(TreeNode * root) { return helper(root)->isBST; } ResultType *helper(TreeNode *root) { if (root == NULL) { return new ResultType(true); } // Divide ResultType *left = helper(root->left); ResultType *right = helper(root->right); // Conquer // 先处理不是的情况 if (!left->isBST || !right->isBST) { return new ResultType(false); } if (left->maxNode != NULL && left->maxNode->val >= root->val) { return new ResultType(false); } if (right->minNode != NULL && right->minNode->val <= root->val ) { return new ResultType(false); } // 最后处理复杂的是的情况 ResultType *ret = new ResultType(true); // 首先，是BST ret->minNode = left->minNode != NULL ? left->minNode : root; ret->maxNode = right->maxNode != NULL ? right->maxNode : root; return ret; }

二叉树中最近公共祖先 （Lowest Common Anscestor）

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /* * @param root: The root of binary tree * @return: An integer */ int minDepth(TreeNode * root) { // write your code here if(root == NULL) { return 0; } // Divide int left = minDepth(root->left); int right = minDepth(root->right); // Conquer if(left == 0 && right == 0) { return 1; }else if(left == 0 && right != 0) { return right + 1; }else if(left != 0 && right == 0) { return left + 1; }else { return min(left, right) + 1; } } };

二叉树路径和最大值

public int maxPathSum(TreeNode *root) { if(root == NULL) { return 0; } // Divide int left = maxPathSum(root->left); int right = maxPathSum(root->right); // Conquer //root->leaf return max(left, right) + root->val; // root->any return max(max(left, right), 0) + root->val; // 也就是说如果是到any节点，那么如果是负数，我们不如不要他，但是如果是到leaf则不行，不管是不是负的，你都必须走到leaf才行。 } // any->any 用到两个分治法 class ResultType { public: int any2any; int root2any; ResultType(int root2any, int any2any) { this->root2any = root2any; this->any2any = any2any; } }; class Solution { public: /* * @param root: The root of binary tree. * @return: An integer */ int maxPathSum(TreeNode * root) { // write your code here return helper(root).any2any; } ResultType helper(TreeNode *root) { //illegal 这种情况是不合法，找不到 不是找到为0 if(root == NULL) { return ResultType(INT_MIN, INT_MIN); } // Divide ResultType left = helper(root->left); ResultType right = helper(root->right); // Conquer int any2any = max(left.any2any, right.any2any); int root2any = max(0, max(left.root2any, right.root2any)) + root->val; any2any = max(any2any, max(left.root2any, 0) + max(right.root2any, 0) + root->val); return ResultType(root2any, any2any); } };