知识点 二叉树遍历 前序遍历:先访问根节点,再前序遍历左子树,再前序遍历右子树 中序遍历:先中序遍历左子树,再访问根节点,再中序遍历右子树 后序遍历:先后序遍历左子树,再后序遍历右子树,再访问根节点
注意点
前序遍历 例题:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
递归 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : vector<int > ans; vector<int > preorderTraversal (TreeNode* root) { if (root==NULL ) return ans; ans.push_back (root->val); preorderTraversal (root->left); preorderTraversal (root->right); return ans; } };
非递归 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : vector<int > preorderTraversal (TreeNode* root) { vector<int > ans; if (root==NULL ) return ans; stack<TreeNode*> st; TreeNode *cur=root; while (cur!=NULL ||!st.empty ()) { while (cur!=NULL ) { ans.push_back (cur->val); st.push (cur); cur=cur->left; } cur=st.top (); st.pop (); cur=cur->right; } return ans; } };
也可以这么写
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : vector<int > preorderTraversal (TreeNode* root) { vector<int > ans; if (root==NULL ) return ans; stack<TreeNode*> st; st.push (root); while (!st.empty ()) { auto cur=st.top (); st.pop (); ans.push_back (cur->val); if (cur->right) st.push (cur->right); if (cur->left) st.push (cur->left); } return ans; } };
中序遍历 例题:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
递归 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : vector<int >ans; vector<int > inorderTraversal (TreeNode* root) { if (root==NULL ) return ans; inorderTraversal (root->left); ans.push_back (root->val); inorderTraversal (root->right); return ans; } };
后序遍历: 例题:https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
递归: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : vector<int > ans; vector<int > postorderTraversal (TreeNode* root) { if (root==NULL ) return ans; postorderTraversal (root->left); postorderTraversal (root->right); ans.push_back (root->val); return ans; } };
分治法应用 先分别处理局部,再合并结果
适用场景
分治法模板
ResultType traversal (TreeNode *root) { if (!root) { } auto left = traversal (root->left); auto right = traversal (root->right); auto result = merge (left, right); return result; }
典型示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 vector<int > preOrderTraversal (TreeNode *root) { return divideAndConquer (root); }vector<int > divideAndConquer (TreeNode *root) { vector<int > result; if (!root) { return result; } auto left = divideAndConquer (root->left); auto right = divideAndConquer (root->right); result.push_back (root->val); result.insert (result.end (), left.begin (), left.end ()); result.insert (result.end (), right.begin (), right.end ()); return result; }
归并排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 template <typename T>static void MergeSort (T arr[], int len) { auto tmp = new T[len]; mergeSort (arr, 0 , len - 1 , tmp); delete [] tmp; }template <typename T>static void mergeSort (T arr[], int begin, int end, T tmp[]) { if (begin + 1 >= end) { return ; } auto mid = begin + (end - begin) / 2 ; auto begin1 = begin; auto end1 = mid; auto begin2 = mid + 1 ; auto end2 = end; mergeSort (arr, begin1, end1, tmp); mergeSort (arr, begin2, end2, tmp); auto index = begin; while (begin1 <= end1 && begin2 <= end2) { tmp[index++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++]; } while (begin1 <= end1) { tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { tmp[index++] = arr[begin2++]; } for (int i = begin; i <= end; ++i) { arr[i] = tmp[i]; } }
快速排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 template <typename T>static void QuickSort (T arr[], int len) { quickSort (arr, 0 , len - 1 ); }template <typename T>static void quickSort (T arr[], int begin, int end) { if (begin >= end) { return ; } auto pivot = partition (arr, begin, end); quickSort (arr, begin, pivot - 1 ); quickSort (arr, pivot + 1 , end); }template <typename T>static int partition (T arr[], int begin, int end) { auto base = arr[end]; auto lessInsert = begin; for (int i = begin; i < end; ++i) { if (arr[i] < base) { swap (arr[lessInsert++], arr[i]); } } swap (arr[lessInsert], arr[end]); return lessInsert; }
常见题目示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution {public : int maxDepth (TreeNode* root) { if (root==NULL ) return 0 ; int left=maxDepth (root->left); int right=maxDepth (root->right); if (left>right) return left+1 ; else return right+1 ; } };
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3 / 9 20 / 15 7 返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
/ 2 2 / 3 3 / 4 4 返回 false 。
从底至顶 思路:分治法,左边平衡 && 右边平衡 && 左右两边高度 <= 1, 因为需要返回是否平衡及高度,要么返回两个数据,要么合并两个数据, 所以用-1 表示不平衡,>0 表示树高度(二义性:一个变量有两种含义)。
注意
一般工程中,结果通过两个变量来返回,不建议用一个变量表示两种含义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution {public : bool isBalanced (TreeNode* root) { if (maxDepth (root)==-1 ) { return false ; } return true ; } int maxDepth (TreeNode *root) { if (root==NULL ) { return 0 ; } int left=maxDepth (root->left); int right=maxDepth (root->right); if (left==-1 ||right==-1 ||left-right>1 ||right-left>1 ) { return -1 ; } if (left>right) { return left+1 ; } return right+1 ; } };
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入: [1,2,3]
/ 2 3
输出: 6 示例 2:
输入: [-10,9,20,null,null,15,7]
-10 / 9 20 / 15 7
输出: 42
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : int maxPathSum (TreeNode* root) { int res=INT_MIN; helper (root,res); return res; } int helper (TreeNode*root,int &val) { if (root==NULL ) return 0 ; int left=max (0 ,helper (root->left,val)); int right=max (0 ,helper (root->right,val)); int lmr=root->val+left+right; int ret=root->val+max (left,right); val=max (val,max (lmr,ret)); return ret; } };
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科 中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先 )。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
思路:分治法,有左子树的公共祖先或者有右子树的公共祖先,就返回子树的祖先,否则返回根节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : TreeNode* lowestCommonAncestor (TreeNode* root, TreeNode* p, TreeNode* q) { if (root==NULL ) return root; if (root==p||root==q) return root; auto left=lowestCommonAncestor (root->left,p,q); auto right=lowestCommonAncestor (root->right,p,q); if (left!=NULL &&right!=NULL ) return root; if (left!=NULL ) return left; if (right!=NULL ) return right; return NULL ; } };
BFS 层次应用 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution {public : vector<vector<int >> levelOrder (TreeNode* root) { vector<vector<int >> res; if (root==NULL ) return res; queue<TreeNode *> q; q.push (root); while (!q.empty ()) { int currentLevelSize=q.size (); vector<int > level; for (int i=0 ;i<currentLevelSize;i++) { auto cur=q.front (); level.push_back (cur->val); q.pop (); if (cur->left) q.push (cur->left); if (cur->right) q.push (cur->right); } res.push_back (level); } return res; } };
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
思路:在层级遍历的基础上,翻转一下结果即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution {public : vector<vector<int >> levelOrderBottom (TreeNode* root) { vector<vector<int >> res; if (root==NULL ) return res; queue<TreeNode*>q; q.push (root); while (!q.empty ()) { int curLevelSize=q.size (); vector<int > curLevel; for (int i=0 ;i<curLevelSize;i++) { auto cur=q.front (); q.pop (); curLevel.push_back (cur->val); if (cur->left) q.push (cur->left); if (cur->right) q.push (cur->right); } res.push_back (curLevel); } reverse (res.begin (),res.end ()); return res; } };
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如: 给定二叉树 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7 返回锯齿形层次遍历如下:
[ [3], [20,9], [15,7] ]
思路:特定层结果翻转即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : vector<vector<int >> zigzagLevelOrder (TreeNode* root) { vector<vector<int >> res; if (root==NULL ) return res; queue<TreeNode*> q; q.push (root); bool toggle=false ; while (!q.empty ()) { int curLevelSize=q.size (); vector<int > curLevel; for (int i=0 ;i<curLevelSize;i++) { auto cur=q.front (); q.pop (); curLevel.push_back (cur->val); if (cur->left) q.push (cur->left); if (cur->right) q.push (cur->right); } if (toggle) { reverse (curLevel.begin (),curLevel.end ()); } toggle=!toggle; res.push_back (curLevel); } return res; } };
二叉搜索树应用 给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
中序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : bool isValidBST (TreeNode* root) { if (root==NULL ) return true ; vector<int >res; inOrder (root,res); for (int i=0 ;i<res.size ()-1 ;i++) { if (res[i]>=res[i+1 ]) return false ; } return true ; } void inOrder (TreeNode*root,vector<int > &res) { if (root==NULL ) return ; inOrder (root->left,res); res.push_back (root->val); inOrder (root->right,res); } };
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : TreeNode* insertIntoBST (TreeNode* root, int val) { if (root==nullptr ) return new TreeNode (val); if (root->val<val) { root->right=insertIntoBST (root->right,val); } else { root->left=insertIntoBST (root->left,val); } return root; } };