一级类目 二级类型/题目 三级类目/题目

二叉树的遍历 144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
剑指 Offer 32 - I. 从上到下打印二叉树
剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - III. 从上到下打印二叉树 III
107. 二叉树的层序遍历 II
面试题34. 二叉树中和为某一值的路径
构造二叉树

105. 从前序与中序遍历序列构造二叉树

| | | | |

106. 从中序与后序遍历序列构造二叉树

| | | | |

889. 根据前序和后序遍历构造二叉树

| | | | |

108. 将有序数组转换为二叉搜索树

| | | | |

109. 有序链表转换二叉搜索树

| | | | |

114. 二叉树展开为链表

| | | | |

617. 合并二叉树

| | | | 输出二叉树 |

剑指 Offer 37. 序列化二叉树

| | | |



二叉树的验证 |

100. 相同的树

| | | | |

剑指 Offer 28. 对称的二叉树

| | | | |

剑指 Offer 55 - II. 平衡二叉树

| | | | |

98. 验证二叉搜索树

| | | | |

958. 二叉树的完全性检验

| | | | |

剑指 Offer 26. 树的子结构

| | | | |

572. 另一棵树的子树

| | | | |

剑指 Offer 27. 二叉树的镜像

| | | | | 156.上下翻转二叉树 | |

二叉树

二叉树的遍历

144. 二叉树的前序遍历

  • 解法一：递归

    1. class Solution {
    2. public:
    3.   vector<int> res;
    5.   void preOrder(TreeNode *root) {
    6.       if (!root)return;
    7.       res.push_back(root->val);
    8.       preOrder(root->left);
    9.       preOrder(root->right);
    10.   }
    12.   vector<int> preorderTraversal(TreeNode *root) {
    13.       preOrder(root);
    14.       return res;
    15.   }
    16. };

  • 解法二：使用栈迭代

image.png

  1. class Solution {
  2. public:
  3.     vector<int> res;
  5.     // root ,left,right
  6.     vector<int> preorderTraversal(TreeNode *root) {
  7.         if (!root)return res;
  8.         stack<TreeNode *> st;
  9.         TreeNode *node = root;
  10.         while (!st.empty() || node) {
  11.             while (node) {
  12.                 res.emplace_back(node->val);
  13.                 st.emplace(node);
  14.                 node = node->left;
  15.             }
  16.             node = st.top();
  17.             st.pop();
  18.             node = node->right;
  19.         }
  20.         return res;
  21.     }
  22. };

94. 二叉树的中序遍历

  • 解法一

    1. class Solution {
    2. public:
    3.   vector<int> res;
    5.   void inorder(TreeNode *root) {
    6.       if (!root)return;
    7.       inorder(root->left);
    8.       res.push_back(root->val);
    9.       inorder(root->right);
    10.   }
    12.   vector<int> inorderTraversal(TreeNode *root) {
    13.       inorder(root);
    14.       return res;
    15.   }
    16. };

  • 解法二

    1. class Solution {
    2. public:
    3.   vector<int> res;
    5.   // root ,left,right
    6.   vector<int> inorderTraversal(TreeNode *root) {
    7.       if (!root)return res;
    8.       stack<TreeNode *> stack;
    9.       while (root || !stack.empty()) {
    10.           while (root) {
    11.               stack.emplace(root);
    12.               root = root->left;
    13.           }
    14.           root = stack.top();
    15.           stack.pop();
    16.           res.emplace_back(root->val);
    17.           root = root->right;
    18.       }
    19.       return res;
    20.   }
    21. };

    145. 二叉树的后序遍历

  • 解法一：

    1. class Solution {
    2. public:
    3.   vector<int> res;
    5.   void postOrder(TreeNode *root) {
    6.       if (!root)return;
    7.       postOrder(root->left);
    8.       postOrder(root->right);
    9.       res.emplace_back(root->val);
    10.   }
    12.   //left right root
    13.   vector<int> postorderTraversal(TreeNode *root) {
    14.       postOrder(root);
    15.       return res;
    16.   }
    17. };

    剑指 Offer 32 - I. 从上到下打印二叉树

    ```cpp class Solution { public: vector res; vector levelOrder(TreeNode *root) {

    1.   if (root == nullptr)
    2.   {
    3.       return res;
    4.   }
    5.   queue<TreeNode *> queue;
    6.   queue.push(root);
    7.   while (!queue.empty())
    8.   {
    9.       int size = queue.size();
    10.       for (int i = 0; i < size; i++)
    11.       {
    12.           TreeNode *tmp = queue.front();
    13.           res.push_back(tmp->val);
    14.           queue.pop();
    15.           if (tmp->left)
    16.           {
    17.               queue.push(tmp->left);
    18.           }
    19.           if (tmp->right)
    20.           {
    21.               queue.push(tmp->right);
    22.           }
    23.       }
    24.   }
    25.   return res;

    } };

  1. <a name="aDF0i"></a>
  2. #### [剑指 Offer 32 - II. 从上到下打印二叉树 II](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)
  3. ```cpp
  4. /**
  5.  * Definition for a binary tree node.
  6.  * struct TreeNode {
  7.  *     int val;
  8.  *     TreeNode *left;
  9.  *     TreeNode *right;
  10.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  11.  * };
  12.  */
  13. class Solution
  14. {
  15. public:
  16.     vector<vector<int>> res;
  17.     vector<vector<int>> levelOrder(TreeNode *root)
  18.     {
  19.         if (root == nullptr)
  20.         {
  21.             return res;
  22.         }
  23.         queue<TreeNode *> queue;
  24.         queue.push(root);
  25.         while (!queue.empty())
  26.         {
  27.             int size = queue.size();
  28.             vector<int> ans;
  29.             for (int i = 0; i < size; i++)
  30.             {
  31.                 TreeNode *tmp = queue.front();
  32.                 ans.push_back(tmp->val);
  33.                 queue.pop();
  34.                 if (i == size - 1)
  35.                 {
  36.                     res.push_back(ans);
  37.                 }
  38.                 if (tmp->left)
  39.                 {
  40.                     queue.push(tmp->left);
  41.                 }
  42.                 if (tmp->right)
  43.                 {
  44.                     queue.push(tmp->right);
  45.                 }
  46.             }
  47.         }
  48.         return res;
  49.     }
  50. };

剑指 Offer 32 - III. 从上到下打印二叉树 III

  1. class Solution
  2. {
  3. public:
  4.     vector<vector<int>> res;
  5.     vector<vector<int>> levelOrder(TreeNode *root)
  6.     {
  7.         if (!root)
  8.         {
  9.             return res;
  10.         }
  11.         queue<TreeNode *> queue;
  12.         queue.push(root);
  13.         int count = 1;
  14.         while (!queue.empty())
  15.         {
  16.             int size = queue.size();
  17.             vector<int> ans;
  18.             for (int i = 0; i < size; i++)
  19.             {
  20.                 TreeNode *node = queue.front();
  21.                 ans.push_back(node->val);
  22.                 queue.pop();
  23.                 if (i == size - 1)
  24.                 {
  25.                     if (!(count & 1))
  26.                     {
  27.                         reverse(ans.begin(), ans.end());
  28.                     }
  29.                     res.push_back(ans);
  30.                 }
  31.                 if (node->left)
  32.                 {
  33.                     queue.push(node->left);
  34.                 }
  35.                 if (node->right)
  36.                 {
  37.                     queue.push(node->right);
  38.                 }
  39.             }
  40.             count += 1;
  41.         }
  42.         return res;
  43.     }
  44. };

107. 二叉树的层序遍历 II

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution
  13. {
  14. public:
  15.     vector<vector<int>> res;
  16.     vector<vector<int>> levelOrderBottom(TreeNode *root)
  17.     {
  18.         if (!root)
  19.         {
  20.             return res;
  21.         }
  22.         queue<TreeNode *> queue;
  23.         queue.push(root);
  24.         while (!queue.empty())
  25.         {
  26.             int size = queue.size();
  27.             vector<int> ans;
  28.             for (int i = 0; i < size; i++)
  29.             {
  30.                 TreeNode *node = queue.front();
  31.                 ans.push_back(node->val);
  32.                 queue.pop();
  33.                 if (i == size - 1)
  34.                 {
  35.                     res.push_back(ans);
  36.                 }
  37.                 if (node->left)
  38.                 {
  39.                     queue.push(node->left);
  40.                 }
  41.                 if (node->right)
  42.                 {
  43.                     queue.push(node->right);
  44.                 }
  45.             }
  46.         }
  47.         reverse(res.begin(),res.end());
  48.         return res;
  49.     }
  50. };

面试题34. 二叉树中和为某一值的路径

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14. vector<vector<int>> res;
  15. vector<int> path;
  16.     vector<vector<int>> pathSum(TreeNode* root, int target) {
  17.         dfs(root,target);
  18.         return res;
  19.     }
  20.     void dfs(TreeNode* root,int target){
  21.         if(root==nullptr){
  22.             return;
  23.         }
  24.         target-=root->val;
  25.         path.push_back(root->val);
  26.         if(target==0&&root->left==nullptr&&root->right==nullptr){
  27.             res.push_back(path);
  28.         }else {
  29.             dfs(root->left,target);
  30.             dfs(root->right,target);
  31.         }
  32.         path.pop_back();    
  33.     }
  34. };

构造二叉树

105. 从前序与中序遍历序列构造二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.   unordered_map<int, int> index;
  16.     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
  17.         int n = inorder.size();
  18.         for (int i = 0; i < n; i++) {
  19.             index[inorder[i]] = i;
  20.         }
  21.         return myselfBuild(preorder, inorder, 0, n - 1, 0, n - 1);
  22.     }
  24.     // 根 [左子树遍历结果] [右子树遍历结果]
  25.     // [左子树遍历结果] 根 [右子树遍历结果]
  26.     TreeNode *myselfBuild(vector<int> &preorder, vector<int> &inorder, int preorder_left,
  27.                           int preorder_right, int inorder_left, int inorder_right) {
  28.         if (preorder_left > preorder_right) {
  29.             return nullptr;
  30.         }
  31.         int inorder_root = index[preorder[preorder_left]];
  32.         TreeNode *root = new TreeNode(inorder[inorder_root]);
  34.         int size_left_subtree = inorder_root - inorder_left;
  36.         root->left = myselfBuild(preorder,
  37.                                  inorder,
  38.                                  preorder_left + 1,
  39.                                  preorder_left + size_left_subtree,
  40.                                  inorder_left, inorder_root - 1);
  42.         root->right = myselfBuild(preorder, 
  43.                                   inorder,
  44.                                   preorder_left + size_left_subtree + 1,
  45.                                   preorder_right,
  46.                                   inorder_root + 1,
  47.                                   inorder_right
  48.         );
  49.         return root;
  50.     }
  52. };

106. 从中序与后序遍历序列构造二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     unordered_map<int, int> index;
  15.     // 不要像105那样将数组也递归 ，容易stackoverflow ,使用一个全局代替;
  16.     vector<int> post;
  18.     TreeNode *buildMySelf(int postorder_left, int postorder_right,
  19.                           int inorder_left, int inorder_right) {
  20.         if (postorder_left > postorder_right || inorder_left > inorder_right) {
  21.             return nullptr;
  22.         }
  23.         int root_val = post[postorder_right];
  24.         int inorder_root = index[root_val];
  26.         TreeNode *root = new TreeNode(root_val);
  28.         int size_left_tree = inorder_root - inorder_left;
  30.         root->left = buildMySelf(
  31.                                  postorder_left,
  32.                                  postorder_left + size_left_tree - 1,
  33.                                  inorder_left,
  34.                                  inorder_root - 1);
  36.         root->right = buildMySelf(
  37.                                   postorder_left + size_left_tree,
  38.                                   postorder_right - 1,
  40.                                   inorder_root + 1,
  41.                                   inorder_right);
  43.         return root;
  46.     }
  47.     // 左子树遍历 右子树遍历 根
  49.     // 左子树遍历 根 右子树遍历
  50.     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
  51.         int n = inorder.size();
  52.         for (int i = 0; i < n; i++) {
  53.             index[inorder[i]] = i;
  54.         }
  55.         post=postorder;
  56.         return buildMySelf(0, n - 1, 0, n - 1);
  57.     }
  58. };

889. 根据前序和后序遍历构造二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.    // 根 左子树遍历 右子树遍历
  15.     // 左子树遍历 右子树遍历 根
  16.     // 1,2,4,5,3,6,7
  17.     // 4,5,2,6,7,3,1
  18.     unordered_map<int, int> postorder_index;
  19.     vector<int> preorderArr;
  21.     TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder) {
  22.         int n = preorder.size();
  23.         for (int i = 0; i < n; i++) {
  24.             postorder_index[postorder[i]] = i;
  25.         }
  26.         preorderArr = preorder;
  28.         return buildSubTree(0, n - 1, 0, n - 1);
  30.     }
  32.     TreeNode *buildSubTree(
  33.             int preorder_left, int preorder_right,
  34.             int postorder_left, int postorder_right) {
  35.         if (preorder_left > preorder_right) { return nullptr; }
  37.         TreeNode *root = new TreeNode(preorderArr[preorder_left]);
  39.         if (preorder_left == preorder_right) { return root; }
  41.         // 先序遍历 第二个元素就是左子树 的根节点，也就是2
  42.         // 找到2在后序遍历中的位置 ，后续遍历中2之前全部是左子树部分，这样就可以找到左子树长度;
  43.         int post_left_index = postorder_index[preorderArr[preorder_left + 1]];
  45.         //左子树长度;
  46.         int size_left_subtree = post_left_index - postorder_left + 1;
  48.         // 1,2,4,5,3,6,7
  49.         // 4,5,2,6,7,3,1
  50.         root->left = buildSubTree(
  51.                 preorder_left + 1,
  52.                 preorder_left + size_left_subtree,
  53.                 postorder_left, post_left_index
  54.         );
  56.         root->right = buildSubTree(
  57.                 preorder_left + size_left_subtree + 1,
  58.                 preorder_right,
  59.                 post_left_index + 1,
  60.                 postorder_right - 1
  61.         );
  62.         return root;
  63.     }
  65. };

108. 将有序数组转换为二叉搜索树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.      TreeNode *sortedArrayToBST(vector<int> &nums) {
  15.         if (nums.empty()) {
  16.             return nullptr;
  17.         }
  19.         return buildBinaryTree(nums, 0, nums.size() - 1);
  20.     }
  22.     TreeNode *buildBinaryTree(vector<int> &nums, int left, int right) {
  23.         if (left > right) {
  24.             return nullptr;
  25.         }
  26.         int mid = left + ((right - left) >> 1); 
  27.         TreeNode *root = new TreeNode(nums[mid]);
  28.         root->left = buildBinaryTree(nums, left, mid - 1);
  29.         root->right = buildBinaryTree(nums, mid + 1, right);
  30.         return root;
  31.     }
  32. };

109. 有序链表转换二叉搜索树

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. /**
  12.  * Definition for a binary tree node.
  13.  * struct TreeNode {
  14.  *     int val;
  15.  *     TreeNode *left;
  16.  *     TreeNode *right;
  17.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  18.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  19.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  20.  * };
  21.  */
  22. class Solution {
  23. public:
  24.      ListNode *getMidNode(ListNode *left, ListNode *right) {
  25.         ListNode *fast = left;
  26.         ListNode *slow = left;
  27.         while (fast != right && fast->next!= right) {
  28.             fast = fast->next->next;
  29.             slow = slow->next;
  30.         }
  31.         return slow;
  32.     }
  34.     TreeNode *buildSubTree(ListNode *left, ListNode *right) {
  35.         if (left == right) {
  36.             return nullptr;
  37.         }
  38.         ListNode *mid = getMidNode(left, right);
  39.         TreeNode *root = new TreeNode(mid->val);
  40.         root->left = buildSubTree(left, mid);
  41.         root->right = buildSubTree(mid->next, right);
  42.         return root;
  43.     }
  45.     TreeNode *sortedListToBST(ListNode *head) {
  46.         if (head == nullptr) {
  47.             return nullptr;
  48.         }
  49.         return buildSubTree(head, nullptr);
  50.     }
  51. };

114. 二叉树展开为链表

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.      void flatten(TreeNode *root) {
  15.         while(root){
  16.             if(!root->left){
  17.                 root=root->right;
  18.             }else {
  19.                 TreeNode *prev=root->left;
  20.                 while(prev->right){
  21.                     prev=prev->right;
  22.                 }
  23.                 prev->right=root->right; //将右子树嫁接过来
  24.                 root->right=root->left;
  25.                 root->left=nullptr;
  26.                 root=root->right;
  28.             }
  29.         }
  30.     }
  31. };

617. 合并二叉树

  • 在原来的一个树上做合并操作

    1. TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    2.      if(!root1){
    3.          return root2;
    4.      }
    5.      if(!root2){return root1;}
    6.      root1->val+=root2->val;
    7.      root1->left=mergeTrees(root1->left,root2->left);
    8.      root1->right=mergeTrees(root1->right,root2->right);
    9.      return root1;
    10.   }

  • 在一棵新树上做合并操作

    1. TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    2.      if(!root1){
    3.          return root2;
    4.      }
    5.      if(!root2){return root1;}
    6.      TreeNode* tmp=new TreeNode(root1->val+root2->val);
    7.      tmp->left=mergeTrees(root1->left,root2->left);
    8.      tmp->right=mergeTrees(root1->right,root2->right);
    9.      return tmp;
    10. }

输出二叉树

剑指 Offer 37. 序列化二叉树

二叉树的验证

100. 相同的树

  1.   bool isSameTree(TreeNode *p, TreeNode *q) {
  2.         // 两个要么都是null ，如果有一个是null 则是不相同的;
  3.         if ((p && !q) || (!p && q)) {
  4.             return false;
  5.         }
  6.         if (p == q && !q) {
  7.             return true;
  8.         }
  9.         return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
  10.     }

剑指 Offer 28. 对称的二叉树

  1. bool isSymmetric(TreeNode *root) {
  2.         return !root ? true : recur(root->left, root->right);
  3. }
  5.     bool recur(TreeNode *left, TreeNode *right) {
  6.         if (!left && !right) { return true; }
  7.         if (!left || !right || left->val != right->val) {
  8.             return false;
  9.         }
  10.         return recur(left->left, right->right) && recur(left->right, right->left);
  11.     }

剑指 Offer 55 - II. 平衡二叉树

  1.     int depth(TreeNode *root) {
  2.         if (!root) {
  3.             return 0;
  4.         }
  5.         int left = depth(root->left);
  6.         int right = depth(root->right);
  7.         return max(left, right) + 1;
  8.     }
  10.     bool isBalanced(TreeNode *root) {
  11.         if (!root) {
  12.             return true;
  13.         }
  14.         return abs(depth(root->left) - depth(root->right)) < 2
  15.                && isBalanced(root->left)
  16.                && isBalanced(root->right);
  17.     }

98. 验证二叉搜索树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> res;
  16.     bool isValidBST(TreeNode *root) {
  17.         inOrder(root);
  18.         for (int i = 1; i < res.size(); i++) {
  19.             if (res[i] <= res[i - 1]) {
  20.                 return false;
  21.             }
  22.         }
  23.         return true;
  24.     }
  26.     void inOrder(TreeNode *root) {
  27.         if (!root) {
  28.             return;
  29.         }
  30.         inOrder(root->left);
  31.         res.push_back(root->val);
  32.         inOrder(root->right);
  33.     }
  34. };

958. 二叉树的完全性检验

  1. bool isCompleteTree(TreeNode *root) {
  2.         queue<TreeNode *> q;
  3.         q.push(root);
  4.         bool hasNull = false;
  5.         while (!q.empty()) {
  6.             TreeNode *curr = q.front();
  7.             q.pop();
  8.             if (curr == nullptr) {
  9.                 hasNull = true;
  10.                 continue;
  11.             } else {
  12.                 if (hasNull) {
  13.                     return false;
  14.                 }
  15.                 q.push(curr->left);
  16.                 q.push(curr->right);
  17.             }
  18.         }
  19.         return true;
  20.     }

993. 二叉树的堂兄弟节点

层序遍历时判断父亲节点个数

  1.  bool isCousins(TreeNode *root, int x, int y) {
  2.         queue<pair<TreeNode *, TreeNode *>> q;
  3.         q.push({root, nullptr});
  4.         while (!q.empty()) {
  5.             int n = q.size();
  6.             vector<TreeNode *> cur_parent;
  7.             for (int i = 0; i < n; i++) {
  8.                 auto[cur, parent] = q.front();
  9.                 q.pop();
  10.                 if (cur->val == x || cur->val == y) {
  11.                     cur_parent.push_back(parent);
  12.                 }
  13.                 if (cur->left) {
  14.                     q.push({cur->left, cur});
  15.                 }
  16.                 if (cur->right) {
  17.                     q.push({cur->right, cur});
  18.                 }
  19.             }
  20.             if (cur_parent.size() == 0) {
  21.                 continue;
  22.             }
  23.             if (cur_parent.size() == 1) {
  24.                 return false;
  25.             }
  26.             if (cur_parent.size() == 2) {
  27.                 return cur_parent[0] != cur_parent[1];
  28.             }
  29.         }
  30.         return false;
  31.     }

剑指 Offer 26. 树的子结构

  1.     bool isSubStructure(TreeNode *A, TreeNode *B) {
  2.         if (!A || !B) {
  3.             return false;
  4.         }
  5.         return (recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
  8.     bool recur(TreeNode *A, TreeNode *B) {
  9.         if (!B) { return true; }
  10.         if (!A || A->val != B->val) {
  11.             return false;
  12.         }
  13.         return recur(A->left, B->left) && recur(A->right, B->right);
  14.     }

572. 另一棵树的子树

  1. bool isSubtree(TreeNode *A, TreeNode *B) {
  2.         //两棵树 任一一棵都不允许为空
  3.         if (!A) {
  4.             return false;
  5.         }
  6.         if (isSameTree(A, B)) {
  7.             return true;
  8.         }
  9.         return isSubtree(A->left, B) || isSubtree(A->right, B);
  10.     }
  12.     bool isSameTree(TreeNode *q, TreeNode *p) {
  13.         if ((!q && p) || (!p && q)) {
  14.             return false;
  15.         }
  16.         if (p == q && !q) {
  17.             return true;
  18.         }
  19.         return q->val == p->val && isSameTree(q->left, p->left) && isSameTree(p->right, q->right);
  20.     }

二叉树翻转

剑指 Offer 27. 二叉树的镜像

  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. *     int val;
  5. *     TreeNode *left;
  6. *     TreeNode *right;
  7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11.     public:
  12.     TreeNode* mirrorTree(TreeNode* root) {
  13.         // write code here
  14.         if (root == nullptr) {
  15.             return nullptr;
  16.         }
  17.         TreeNode *tmp = root->left;
  18.         root->left = root->right;
  19.         root->right = tmp;
  20.         mirrorTree(root->right);
  21.         mirrorTree(root->left);
  22.         return root;
  23.     }
  24. };

156.上下翻转二叉树

  1. class Solution {
  2.     public:
  3.     TreeNode *head;
  4.     TreeNode upsideDownBinaryTree(TreeNode *root){
  5.         if (!root){
  6.             return root;
  7.         }
  8.         dfs(root);
  9.         return head;
  10.     }
  12.     TreeNode *dfs(TreeNode *root){
  13.         if (!root){
  14.             return false;
  15.         }
  16.         //对于任意一个节点,它的右节点变成左子结点的左子结点，它自己变成它左子结点的右子节点。
  17.         if (!root->left && !root->right){
  18.             if (!head){
  19.                 head = root;
  20.             }
  21.             return root;
  22.         }
  23.         TreeNode* left=dfs(root->left);
  24.         TreeNode* right=dfs(root->right);
  25.         if(!left){
  26.             left->left=right;
  27.             left->right=root;
  28.         }
  29.         root->left=nullptr;
  30.         root->right=nullptr;
  31.         return root;
  32.     }

二叉树的深度和直径

剑指 Offer 55 - I. 二叉树的深度

  1. class Solution {
  2. public:
  3.     int maxDepth(TreeNode* root) {
  4.        if(!root){
  5.            return  0;
  6.        }
  7.        int left=maxDepth(root->left);
  8.        int right=maxDepth(root->right);
  9.        return max(left,right)+1;
  10.     }
  11. };

111. 二叉树的最小深度

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.       int minDepth(TreeNode *root) {
  15.             if (!root) { return 0; }
  16.         queue<pair<TreeNode *, int>> q;
  17.         q.push({root, 1});
  18.         while (!q.empty()) {
  19.             auto t = q.front();
  20.             q.pop();
  21.             TreeNode *now = t.first;
  22.             int nowDepth = t.second;
  23.             if (!now->left && !now->right) {
  24.                 return nowDepth;
  25.             }
  26.             if (now->left) {
  27.                 q.push({now->left, nowDepth + 1});
  28.             }
  29.             if (now->right) {
  30.                 q.push({now->right, nowDepth + 1});
  31.             }
  32.         }
  33.         return -1;
  34.     }
  35. };

543. 二叉树的直径

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.    int maxd = 0;
  16.     int diameterOfBinaryTree(TreeNode *root) {
  17.         depth(root);
  18.         return maxd;
  19.     }
  20.     /** 
  21.      * 遍历 左右 最深的同时维护一个  maxd 
  22.      * @param root 
  23.      * @return 
  24.      */
  26.     int depth(TreeNode *root) {
  27.         if (!root) {
  28.             return 0;
  29.         }
  31.         int left = depth(root->left);
  32.         int right = depth(root->right);
  33.         maxd = max(left + right, maxd);
  34.         return max(left, right) + 1;
  35.     }
  36. };

257. 二叉树的所有路径

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  15.     vector<string> res;
  16.     string path;
  17.     vector<string> binaryTreePaths(TreeNode* root) {
  18.        dfs(root,"");
  19.        return res;
  20.     }
  21.     void dfs(TreeNode* root,string path){
  22.         if(!root){
  23.             return;
  24.         }
  25.        if(!root->left && !root->right){
  26.            path+=to_string(root->val);
  27.            res.push_back(path);
  28.            return;
  29.        }
  30.        path+=to_string(root->val)+"->";
  31.        dfs(root->left,path);
  32.        dfs(root->right,path);
  33.     }
  34. };

112. 路径总和

  1. class Solution {
  2. public:
  4.     bool hasPathSum(TreeNode* root, int targetSum) {
  5.        return dfs(root,0,targetSum);
  6.     }
  8.     bool dfs(TreeNode* root,int tmpSum,int targetSum){
  9.         if(!root){return false;}
  10.         tmpSum+=root->val;
  11.         if(!root->left && !root->right){
  12.             return tmpSum==targetSum;
  13.         }else {
  14.             return dfs(root->left,tmpSum,targetSum)
  15.             || dfs(root->right,tmpSum,targetSum);
  16.         }
  17.     }
  18. };