1. 算法思想

作为（单）链表的升级版，我们通常接触的树都是二叉树（binary tree），即每个节点最多有
两个子节点；且除非题目说明，默认树中不存在循环结构。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2.常见题型

2.1 树的递归

对于一些简单的递归题，某些LeetCode 达人喜欢写one-line code，即用一行代码解决问题，
把if-else 判断语句压缩成问号冒号的形式。

LeetCode-104. Maximum Depth of Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, return its maximum depth.https://blog.csdn.net/qq_15711195/article/details/122390238LeetCode-110. Balanced Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given a binary tree, determine if it is height-balanced.https://blog.csdn.net/qq_15711195/article/details/122288238LeetCode-543. Diameter of Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, returnthe length of thediameterof the tree. Thediameterof a binary tree is thelengthof the longest path between any two nodes in a tree. This path may or may not pass through theroot.https://blog.csdn.net/qq_15711195/article/details/122392821LeetCode-112. Path Sum [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree and an integertargetSum, returntrueif the tree has aroot-to-leafpath such that adding up all the values along the path equalstargetSum. Aleafis a node with no children.https://blog.csdn.net/qq_15711195/article/details/126316873LeetCode-113. Path Sum II [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree and an integertargetSum, returnallroot-to-leafpaths where the sum of the node values in the path equalstargetSum. Each path should be returned as a list of the nodevalues, not node references.https://blog.csdn.net/qq_15711195/article/details/126317281LeetCode-437. Path Sum III [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree and an integertargetSum, returnthe number of paths where the sum of the valuesalong the path equalstargetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only ...https://blog.csdn.net/qq_15711195/article/details/126239920LeetCode-101. Symmetric Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree,check whether it is a mirror of itself(i.e., symmetric around its center).https://blog.csdn.net/qq_15711195/article/details/126317542LeetCode-572. Subtree of Another Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given the roots of two binary treesrootandsubRoot, returntrueif there is a subtree ofrootwith the same structure and node values ofsubRootandfalseotherwise. A subtree of a binary treetreeis a tree that consists of a node intreeand all of th...https://blog.csdn.net/qq_15711195/article/details/126331459LeetCode-1110. Delete Nodes And Return Forest [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, each node in the tree has a distinct value.After deleting all nodes with a value into_delete, we are left with a forest (a disjoint union of trees). Return the roots of the trees in the remaining forest. https://blog.csdn.net/qq_15711195/article/details/126320648

2.2 层次遍历

LeetCode-637. Average of Levels in Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, returnthe average value of the nodes on each level in the form of an array. Answers within10-5of the actual answer will be accepted.https://blog.csdn.net/qq_15711195/article/details/126321340

2.3 前中后序遍历

前序遍历先遍历父结点，再遍历左结点，最后遍历右节点

void preorder(TreeNode* root) {
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

中序遍历先遍历左节点，再遍历父结点，最后遍历右节点

void inorder(TreeNode* root) {
    inorder(root->left);
    visit(root);
    inorder(root->right);
}

后序遍历先遍历左节点，再遍历右结点，最后遍历父节点

void postorder(TreeNode* root) {
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

 已知二叉树，求三种序列

LeetCode-94. Binary Tree Inorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客

leetcode单词接龙2-Algorithms:算法学习笔记

zip 星 59KB

下载

LeetCode-145. Binary Tree Postorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客

已知两种序列，重建二叉树

LeetCode-105. Construct Binary Tree from Preorder and Inorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客Given two integer arrayspreorderandinorderwherepreorderis the preorder traversal of a binary tree andinorderis the inorder traversal of the same tree, construct and returnthe binary tree.https://blog.csdn.net/qq_15711195/article/details/122906206?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22122906206%22%2C%22source%22%3A%22qq_15711195%22%7DLeetCode-106. Construct Binary Tree from Inorder and Postorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客Given two integer arraysinorderandpostorderwhereinorderis the inorder traversal of a binary tree andpostorderis the postorder traversal of the same tree, construct and returnthe binary tree.https://blog.csdn.net/qq_15711195/article/details/126339392

LeetCode-889. Construct Binary Tree from Preorder and Postorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客Given two integer arrays,preorderandpostorderwherepreorderis the preorder traversal of a binary tree ofdistinctvalues andpostorderis the postorder traversal of the same tree, reconstruct and returnthe binary tree.https://blog.csdn.net/qq_15711195/article/details/126334214

2.4 二叉查找树

LeetCode-637. Average of Levels in Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, returnthe average value of the nodes on each level in the form of an array. Answers within10-5of the actual answer will be accepted.https://blog.csdn.net/qq_15711195/article/details/126321340LeetCode-105. Construct Binary Tree from Preorder and Inorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客Given two integer arrayspreorderandinorderwherepreorderis the preorder traversal of a binary tree andinorderis the inorder traversal of the same tree, construct and returnthe binary tree.https://blog.csdn.net/qq_15711195/article/details/122906206LeetCode-144. Binary Tree Preorder Traversal [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, returnthe preorder traversal of its nodes' values.https://blog.csdn.net/qq_15711195/article/details/126322090LeetCode-99. Recover Binary Search Tree [C++][Java]_贫道绝缘子的博客-CSDN博客You are given therootof a binary search tree (BST), where the values ofexactlytwo nodes of the tree were swapped by mistake.Recover the tree without changing its structure.https://blog.csdn.net/qq_15711195/article/details/126328221LeetCode-669. Trim a Binary Search Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary search tree and the lowest and highest boundaries aslowandhigh, trim the tree so that all its elements lies in[low, high]. Trimming the tree shouldnotchange the relative structure of the elementshttps://blog.csdn.net/qq_15711195/article/details/126328363LeetCode-208. Implement Trie (Prefix Tree) [C++][Java]_贫道绝缘子的博客-CSDN博客​Atrie(pronounced as "try") orprefix treeis a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.https://blog.csdn.net/qq_15711195/article/details/126328615LeetCode-226. Invert Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, invert the tree, and returnits root.https://blog.csdn.net/qq_15711195/article/details/126329758LeetCode-572. Subtree of Another Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given the roots of two binary treesrootandsubRoot, returntrueif there is a subtree ofrootwith the same structure and node values ofsubRootandfalseotherwise. A subtree of a binary treetreeis a tree that consists of a node intreeand all of th...https://blog.csdn.net/qq_15711195/article/details/126331459LeetCode-101. Symmetric Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree,check whether it is a mirror of itself(i.e., symmetric around its center).https://blog.csdn.net/qq_15711195/article/details/126317542LeetCode-404. Sum of Left Leaves [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, returnthe sum of all left leaves. Aleafis a node with no children. Aleft leafis a leaf that is the left child of another node.https://blog.csdn.net/qq_15711195/article/details/126331670LeetCode-513. Find Bottom Left Tree Value [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a binary tree, return the leftmost value in the last row of the tree.https://blog.csdn.net/qq_15711195/article/details/126331850LeetCode-538. Convert BST to Greater Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.https://blog.csdn.net/qq_15711195/article/details/126332103LeetCode-235. Lowest Common Ancestor of a Binary Search Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.https://blog.csdn.net/qq_15711195/article/details/122254051LeetCode-236. Lowest Common Ancestor of a Binary Tree [C++][Java]_贫道绝缘子的博客-CSDN博客Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.https://blog.csdn.net/qq_15711195/article/details/122254830LeetCode-530. Minimum Absolute Difference in BST [C++][Java]_贫道绝缘子的博客-CSDN博客Given therootof a Binary Search Tree (BST), returnthe minimum absolute difference between the values of any two different nodes in the tree.https://blog.csdn.net/qq_15711195/article/details/126332933

LeetCode-109. Convert Sorted List to Binary Search Tree [C++][Java]_贫道绝缘子的博客-CSDN博客

https://blog.csdn.net/qq_15711195/article/details/126339535?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22126339535%22%2C%22source%22%3A%22qq_15711195%22%7D

LeetCode-653. Two Sum IV - Input is a BST [C++][Java]_贫道绝缘子的博客-CSDN博客