:seedling:树

94.二叉树的中序遍历
144.二叉树的前序遍历
145.二叉树的后序遍历
98.验证二叉搜索树
101.对称二叉树
102.二叉树的层序遍历
107.二叉树的层次遍历II
103.二叉树的锯齿形层次遍历
104.二叉树的最大深度
110.平衡二叉树
111.二叉树的最小深度
112.路径总和
124.二叉树中的最大路径和
230.二叉搜索树中第K小的元素
226.翻转二叉树
236.二叉树的最近公共祖先
513.找树左下角的值
617.合并二叉树
687.最长同值路径
671.二叉树中第二小的节点
669.修剪二叉搜索树
701.二叉搜索树中的插入操作

二叉树的中序遍历

Leetcode给定一个二叉树，返回它的迭代中序遍历。

解题思路

使用辅助栈，中序遍历是访问顺序左-中-右

所以每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int>res;
    stack<TreeNode*>sck;
    TreeNode*cur=root;
    while(cur || !sck.empty()){
        while(cur){
            sck.push(cur);
            cur=cur->left;
        }
        cur=sck.top();
        res.push_back(cur->val);
        sck.pop();
        cur=cur->right;
    }
    return res;
}

二叉树的前序遍历

Leetcode

解题思路

非递归实现需要辅助栈
因为栈是先进后出，而前序遍历顺序是：root => left => right 所以right先入栈left后入栈

由于一开始的left和right的地址需要通过root结点获得，所以开始需要先将root入栈

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

二叉树的后序遍历

Leetcode

解题思路

后序遍历顺序left => right => root ,变换的前序遍历顺序root => right => left，结果反转则为后序

前序遍历 + 反转结果即可

vector<int> postorderTraversal(TreeNode* root) {
    if(root == NULL) return {};
    stack<TreeNode*> sck;
    vector<int> res;
    sck.push(root);
    TreeNode* cur = NULL;
    while(!sck.empty()){
        cur = sck.top();
        res.push_back(cur->val);
        sck.pop();
        if(cur->left) sck.push(cur->left);
        if(cur->right) sck.push(cur->right);
    }
    return reverse(res);
}

vector<int> reverse(vector<int> arr){
    vector<int> res;
    for(int i=arr.size()-1; i>=0; --i){
        res.push_back(arr[i]);
    }
    return res;
}

验证二叉搜索树

leetcode给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路

二叉搜索树的典型特点：中序遍历就是一个升序的序列，所以验证的方法就显而易见
中序遍历存入数组，验证数组是否是严格单调递增的

看大佬得题解还有更简洁的方法 : 因为是中序遍历，所以只要维护一个记录上一个结点值得变量，每遍历一个点进行一次比较和更新，如果发现小于上个结点值就返回false，注意比较和更新得顺序不能反。

vector<int> res;
bool isValidBST(TreeNode* root) {
    inorder(root);
    for (int i = 1; i < res.size(); ++i) {
        if (res[i - 1] >= res[i]) 
            return false; 
    }
    return true;
}

void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    res.push_back(root->val);
    inorder(root->right);
}

更简洁得方式：

long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
    if (root == null)  return true;
    if (!isValidBST(root.left)) return false; 
    if (root.val <= pre)  return false; 
    pre = root.val;
    return isValidBST(root.right);
}

对称二叉树

Leetcode给定一个二叉树，检查它是否是镜像对称的。

解题思路

双指针再树中应用。
两个指针分别递归遍历两颗树。

两棵树要想对称，首先他们的子树必须对称，其次他们的根结点必须相等，可以使用后序遍历

bool isSymmetric(TreeNode* root) {
     if (root == NULL) return true;
     return isSymmetric(root->left, root->right);
 }

 bool isSymmetric(TreeNode* left, TreeNode* right){
   if (left == NULL && right == NULL) return true;
   if (left == NULL || right == NULL) return false;
   return isSymmetric(left->left, right->right) && 
          	isSymmetric(left->right, right->left) &&
          	left->val == right->val;  
 }

二叉树的层序遍历

leetcode给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例

3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

解题思路

典型的BFS遍历二叉树，使用了队列，

牢记模板，注意：输出的数组是二维数组，并不是简单的遍历，中间需要size变量来记录每一行的个数。

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int> > res; 
    queue<TreeNode*> que;
    if (root) que.push(root);
    TreeNode* cur = NULL; 
    while (!que.empty()) {
        int size = que.size();
        vector<int> level;
        while (size--) {               
            cur = que.front();
            que.pop();
            level.push_back(cur->val);
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
        } 
        if (!level.empty()) {
            res.push_back(level);
        }
    }
    return res;
}

二叉树的层次遍历II

leetcode给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

解题思路

基本过程与上题的层序遍历一样，

区别在对结果的处理，两种方式：reverse()反转结果，或者插入的时候用头插法，但是因为使用的是vector所以头插法效率极低。

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int> > res;
    TreeNode* cur = NULL;
    if (root != NULL) que.push(root);
    while (!que.empty()) {
        int size = que.size();
        vector<int> level;
        while (size--) {
            cur = que.front();
            que.pop();
            level.push_back(cur->val);
            if (cur->left !=NULL) que.push(cur->left);
            if (cur->right !=NULL) que.push(cur->right);
        }
        res.push_back(level);
        //res.insert(res.begin(),level); // 头插法
    }
    reverse(res.begin(),res.end());
    return res;
}

二叉树的锯齿形层次遍历

leetcode给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

解题思路

主题部分与上两题的层序遍历一致，只是多了一个层数的变量，当层数为偶数从左到右插入，层数为奇数头插法实现从右到左。

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int> > res;
    TreeNode* cur = NULL;
    if (root != NULL) que.push(root);
    int levelNum = 0;
    while (!que.empty()) {
        int size = que.size();
        vector<int> level;
        while (size--) {
            cur = que.front();
            que.pop();
            if (levelNum % 2 == 0) {
                level.push_back(cur->val);
            } else {
                level.insert(level.begin(), cur->val);
            }
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
        }
        levelNum++;
        res.push_back(level);
    }
    return res;
}

二叉树的最大深度

Leetcode给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

解题思路

每个结点得最大深度都需要先知道其两个子结点的最大深度，所以使用后序遍历，先遍历左右子树。

函数意义：返回该结点的最大深度。

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

平衡二叉树

Leetcode给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

解题思路

先判断左右两个子节点是否平衡，再处理当前结点，所以采用后序遍历

使用哈希表来记录每个结点的最高高度，而每个结点的最高高度也是受其左右子结点的影响，所以可以借着第一条的后序遍历来添加每个结点的高度

unordered_map<TreeNode*, int> height;
bool isBalanced(TreeNode* root) {
    if (root == NULL) {
        height[root] = 0;
        return true;
    }
    if(!isBalanced(root->left) || !isBalanced(root->right)) return false;
    height[root] = max(height[root->left], height[root->right]) + 1;
    if(abs(height[root->left] - height[root->right]) > 1) return false;
    return true;
}

二叉树的最小深度

leetcode给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

解题思路

与二叉树最大深度类似，要求每个结点的深度都需要先计算其左右子节点的深度，所以采用后序遍历

注意：有些结点只有一个子结点，再比较左右子结点的最小值时，返回值可能会返回最小值0，所以应该避免这种情况，返回非空的那条子结点深度

int minDepth(TreeNode* root) {
    if (root == NULL) return 0;
    int left = minDepth(root->left);
    int right = minDepth(root->right);
    if(root->left == NULL) return right + 1;
    if(root->right == NULL) return left + 1;
    return min(left, right) + 1;
}

路径总和

leetcode给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

解题思路

从root结点开始遍历，每经过一个结点，sum 值就减去当前节点的权值，直到sum值为0时表示发现路径，由题意路径结尾必须是叶子，所以还需要判断最后是否是叶子结点

因为每个子结点需要处理的sum值都与母结点有关，所以采用自上而下的先序遍历，先处理母结点，再处理子结点

bool hasPathSum(TreeNode* root, int sum) {
    if (root == NULL) return false;
    sum-=root->val;
    if(sum == 0 && root->left == NULL && root->right == NULL) return true;
    return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}

二叉树中的最大路径和

leetcode给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

解题思路

这种可以不经过root结点的路径和，首先想到一条路径一定由三部分构成，左子树路径+中间结点+右子树路径
当前结点的最大路径和与他的左右子树相关，所以先访问子树，是后序遍历。
注意：一个结点返回的不应该是此结点的最大路径和，而应该是单边最大路径给上游
注意：因为路径和可能会有负数出现，可以采用max(0,)的方式去掉负值。

int maxPathSum(TreeNode* root) {
    int sum = INT_MIN;
    maxPathSum(root, sum);
    return sum;
}

int maxPathSum(TreeNode* root, int& sum) {
    if (root == NULL) return 0;
    int left = max(0, maxPathSum(root->left, sum));
    int right = max(0, maxPathSum(root->right, sum));
    sum = max(sum, left + right + root->val);
    return root->val + max(left, right);
}

二叉搜索树中第K小的元素

Leetcode

对于二叉搜索树中序遍历=从小到大排序

需要记录遍历个数的变量

int cnt=0,val=0;
int kthSmallest(TreeNode* root, int k) {
    inorder(root,k);
    return val;
}
void inorder(TreeNode*root,int k){
    if(!root)return;
    inorder(root->left,k);
    if(++cnt==k)val=root->val;
    inorder(root->right,k);
}

翻转二叉树

Leetcode

反转二叉树并返回根节点，交换当前根结点的左右子树

TreeNode* invertTree(TreeNode* root) {
    if(!root)return NULL;
    TreeNode*tmp=invertTree(root->left);
    root->left=invertTree(root->right);
    root->right=tmp;
    return root;
}

二叉树的最近公共祖先

leetcode给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路
首先什么样的结点才会是公共祖先：当某个结点，他的左子树中有p点，右子树中有q点，这个结点即为他俩的公共祖先

后序遍历：因为判断一个结点是否是祖先，需要知道他的左右子树有无p或q结点，所以需要先遍历子树。
注意：当发现中间结点的左右两个子树有一个返回为null说明这条路没有找到，而另一颗子树找到了，那么这个中间结点也需要向上游传递（返回）我找到了的信息.
1
2
3
4
5
6
7
8
9
10
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) return 0;
    TreeNode* left = lowestCommonAncestor(root->left, p ,q);
    TreeNode* right = lowestCommonAncestor(root->right, p ,q);
    if(root == p || root == q) return root;
    if (left != NULL && right != NULL) return root;
    if (left == NULL) return right;
    if (right == NULL) return left;
    return NULL;
}

找树左下角的值

Leetcode

层序遍历（用队列实现），从右往左，最后一个元素即为所求。

前序中序后续（用栈实现）

int findBottomLeftValue(TreeNode* root) {
    if(!root)return 0;
    queue<TreeNode*> NodeQueue;
    int res=0;
    TreeNode*current=new TreeNode(0);
    //先让根节点入队
    NodeQueue.push(root);
    //弹空队列
    while(!NodeQueue.empty()){
        //每个元素出队时，让其子节点入队
        current=NodeQueue.front();
        NodeQueue.pop();
        //保存每层数值
        res=current->val;*
        //每层从右往左入队，最后一个元素即为最底层最左边的值
        if(current->right!=NULL)NodeQueue.push(current->right);
        if(current->left!=NULL)NodeQueue.push(current->left);
    }
    return res;
}

合并二叉树

Leetcode 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

解题思路

函数意义：t2归并到t1里，返回t1
选择t1为主树，更新结点值到t1里。
因为树结构发生变化，所以需要重新链接左右子树

结束条件：当两个都是null结点则返回null，其中一个是null则返回另一个

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if(!t1 && !t2) return NULL;
    if(!t2) return t1;
    if(!t1) return t2;
    t1->val+=t2->val;
    t1->left=mergeTrees(t1->left,t2->left);
    t1->right=mergeTrees(t1->right,t2->right);
    return t1;
}

最长同值路径

Leetcode
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。

解题思路：

寻找最长路径，即需要一个变量ans记录当前最长值，递归时用于比较。
路径可能穿过某个根结点，所以需要遍历每一个结点，将其左子树最长路径加上右子树最长路径。
设计递归函数：返回当前结点下的左右中其中一条最长路径的长度
注意如果结点值与子树的值不连续，路径即为0

路径=结点数-1

int longestUnivaluePath(TreeNode* root) {
    int ans = 0;
    height(root, ans);
    return ans;
}
int height(TreeNode* node, int &ans) {
    if (!root) return 0;
    int left = height(root->left, ans);
    int right = height(root->right, ans);
    left = (root->left && root->val == root->left->val) ? left + 1 : 0;
    right = (root->right && root->val == root->right->val) ? right + 1 : 0;
    ans = max(ans, left + right);
    return max(left, right);
}

二叉树中第二小的节点

Leetcode
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

解题思路

题干关键信息：节点的值不大于它的子节点的值，即root结点就是整棵树的最小值，因此第二小的值只能是min(root->left->val,root->right->val)。
但是当root的值与它其中一个子结点刚好相等时，第二小的值才有可能出现在更深层的子节点中，才需要继续递归搜索第二小值。
函数意义：返回第二小的值。
递归结束条件：null结点或者叶子结点（因为叶子结点的左右子结点都是null，无法访问它）。

哪边找到就返回哪边，都找到则返回较小者。

int findSecondMinimumValue(TreeNode* root) {
    if(!root) return -1;
    if(!root->left && !root->right) return -1;
    int l=root->left->val;
    int r=root->right->val;
    if(root->val == l) l=findSecondMinimumValue(root->left);
    if(root->val == r) r=findSecondMinimumValue(root->right);
    if(l!=-1 && r!=-1) return min(l,r);
    if(l==-1) return r;
    return l;
}

修剪二叉搜索树

Leetcode给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

解题思路

函数意义：修剪二叉树并完返回修剪好的二叉树的根结点
递归结束条件：遇到null
如果根结点的值小于给定的左边界L，那么当前结点及其左子树就会被修剪掉，修剪后的树应该是其右子树，所以返回修剪后的右子树。

涉及到改变树的结构，就需要更新链接，如果当前结点值在范围内，那么修建其左右子树，并且更新左右链接。最后将当前修剪好的子树返回。

TreeNode* trimBST(TreeNode* root, int L, int R) {
    if(!root)return NULL;
    if(root->val < L) return trimBST(root->right,L,R);
    if(root->val > R) return trimBST(root->left,L,R);
    root->left=trimBST(root->left,L,R);
    root->right=trimBST(root->right,L,R);
    return root;
}

二叉搜索树中的插入操作

leetcode给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果

解题思路

凡是看到对一个二叉树进行过修改得题，递归得时候一定要对root的左右两个子树重新赋值
若 val > root.val，插入到右子树。
若 val < root.val，插入到左子树。

若 root == null，即找到了该插入的地方，返回新建的 TreeNode(val)结点。

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (root->val > val) root->left = insertIntoBST(root->left, val);
    else root->right = insertIntoBST(root->right, val);
    return root;
}

450. 删除二叉搜索树中的节点

leetcode给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。

解题思路

必须掌握二叉树的三个性质：
- 中序遍历=递增序列
- 比当前节点大的最小节点，简称中序遍历序列中的后继节点。先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点。
- 比当前节点小的最大节点，简称中序遍历序列中的前驱节点。先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点

当找到要删除的结点后，该结点有4中状态：

如果是叶子结点，删除它就等于向上返回null结点
如果只有一个子树，删除它就等于向上返回他的那唯一一颗子树

如果两颗子树都存在，应该按照第三条性质，左子树链接到右子树中的最左下角的结点后面，然后向上返回右子树。

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;
    if (root->val < key) root->right = deleteNode(root->right, key);
    else if (root->val > key) root->left  = deleteNode(root->left,  key);
    else {	// 找到要删除的结点
        if (root->left == NULL && root->right == NULL) return NULL;	// 该节点是叶子
        if (root->left  == NULL) return root->right;
        if (root->right == NULL) return root->left;
        
        TreeNode* cur = root->right;
        while (cur->left != NULL) {
            cur = cur->left;
        }
        cur->left = root->left;
        return root->right;
    }
    return root;
}