LeetCode：二叉树

发表于 | 分类于

二叉树是数据结构中重要的数据结构，也是面试官经常考的东西。个人对刷题是真的没天分，前面刷后面忘，没办法，或许总结一下印象会更深刻一点，这里主要对有关于树的面试题做一个小的总结。

树的基础知识

二叉树的定义

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。
树具有的特点：

  • 有且只有一个节点没有父节点，该节点称为树的根；
  • 除根外，其余的每个节点有且仅有一个父节点；
  • 树种的每个节点都构成一个以它为根的树； 二叉树在满足树的条件时，满足如下条件：

这里补充一个二叉树性质：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
这里还简要介绍一下满二叉树、完全二叉树、和二叉查找树，因为之前在刷题的时候碰到这类的题。

满二叉树

定义：高度为h，并且由2^h-1个结点组成的二叉树，称为满二叉树。

完全二叉树

定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

面试题：如果一个完全二叉树的结点总数为768个，求叶子结点的个数。
由二叉树的性质知：n0=n2+1，将之带入768=n0+n1+n2中得：768=n1+2n2+1，因为完全二叉树度为1的结点个数要么为0，要么为1，那么就把n1=0或者1都代入公式中，很容易发现n1=1才符合条件。所以算出来n2=383，所以叶子结点个数n0=n2+1=384。
总结规律：如果一棵完全二叉树的结点总数为n，那么叶子结点等于n/2（当n为偶数时）或者(n+1)/2（当n为奇数时）

二叉查找树

定义：二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点，x结点包含关键字key，结点x的key值计为key[x]。如果y是x的左子树中的一个结点，则key[y]<=key[x]；如果y是x的右子树的一个结点，则key[y]>=key[x]。注意，二叉查找树中不存在键值相等的节点。

二叉树遍历

前序遍历

前序遍历的步骤：（1）访问根节点；（2）先递归遍历左子树；（3）后递归遍历右子树；

前序遍历结果：A BDFE CGHI

中序遍历

中序遍历的步骤：按照左子树->根节点->右子树顺序访问。

中序遍历结果：DBEF A GHCI

后序遍历

后序遍历的步骤：按照左子树->右子树->根节点顺序访问。

遍历参考代码（c++）

参考代码：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 void preorder(TreeNode* node) //前序遍历
    {
        if(!node) return;
        std::cout<<node->val<<std::endl;
        preorder(node->left);
        preorder(node->right);
    }
 void inorder(TreeNode* node) //中序遍历
    {
        if(!node) return;
        preorder(node->left);
        std::cout<<node->val<<std::endl;
        preorder(node->right);
    }
 void postorder(TreeNode* node) //后序遍历
    {
        if(!node) return;
        preorder(node->left);
        preorder(node->right);
        std::cout<<node->val<<std::endl;
    }

常见题型（面试题）

题型一、重建二叉树

一般根据要求根据（前序和中序，或者，中序和后序）遍历重建二叉树。

LeetCode 105

题目描述：给定前序遍历和中序遍历结果，重建二叉树。
参考代码：

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
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()||inorder.empty()||inorder.size()!=preorder.size())//非空或者大小不一致
            return NULL;
        TreeNode*res= new TreeNode(preorder[0]);
        vector<int> pre_left;vector<int> pre_right;
        vector<int>in_left;vector<int>in_right;
        int root_index=(find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin());
        for(size_t i=0;i<inorder.size();i++)
        {
            if(i<root_index)
            {
                in_left.push_back(inorder[i]);
                pre_left.push_back(preorder[i+1]);
            }
            if(i>root_index)
            {
                in_right.push_back(inorder[i]);
                pre_right.push_back(preorder[i]);
            }
        }
        res->left=buildTree(pre_left,in_left);
        res->right=buildTree(pre_right,in_right);
        return res;
        
    }

类似的题还有LeetCode 106。

题型二、树的子结构

判断一棵树是否为另一颗树的子树，在做这道题之前，我们先要学会如何判断两个树 是否相等

LeetCode 100

题目描述：判断两颗树是否相等。这题可以使用前序遍历，递归实现，先判断根节点是否相等，然后判断左右子树是否相等。
参考代码：

1
2
3
4
5
6
7
8
bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p&&!q)return true;//都为空
        if(!p||!q)return false;//至少一方为空
        if(p->val==q->val)//如果跟节点相等
            return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);//判断左右子树是否相等
        else
            return false;
    }

理解了上面那道题，其实判断树的子结构就不是很难了

LeetCode 572

思想：我们先从s的根结点开始，跟t比较，如果两棵树完全相同，那么返回true，否则就分别对s的左子结点和右子结点调用递归再次来判断是否相同，只要有一个返回true了，就表示可以找得到。
参考代码：

1
2
3
4
5
bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s) return false; //如果s为空
        if (isSame(s,t)) return true;//如果相等
        return isSubtree(s->left,t) || isSubtree(s->right,t);
    }

题型三、二叉树反转/镜像

LeetCode 226

题目描述：输入二叉树，输出二叉树的镜像。如下图

镜像反转步骤：

了解了上面的步骤，使用递归来解，其实思路会更清晰，跟简单实现。
参考代码：

1
2
3
4
5
6
7
8
9
10
TreeNode* invertTree(TreeNode* root) {
        if(!root)return NULL;
        TreeNode*tmp;
        tmp=root->left;
        root->left=root->right;
        root->right=tmp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }

题型四、二叉树的层次遍历，从上到下打印二叉树

LeetCode 102

思想：简历一个队列，然后将根节点放进去，这时候找根节点的左右子节点，然后pop掉根节点，此时的队列中保存的都是下一层的所有节点，使用循环遍历存放在一个一维向量中，然后将这个一维向量存在二维向量中。
参考代码（循环解法）：

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

参考代码（递归解法）：
递归解法的核心就在于我们需要一个二维数组，和一个变量level，当level递归到上一层的个数，我们新建一个空层，继续往里面加数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>res;
        levelorder(root, 0, res);
        return res; 
    }
    void levelorder(TreeNode*root,int level,vector<vector<int>>&res)
    {
      if(!root)return;
        if (res.size() == level) res.push_back({});
        res[level].push_back(root->val);
        levelorder(root->left, level + 1, res);
        levelorder(root->right, level + 1, res);  
    }      
};

类似的题还有LeetCode 107，只不过这道题是从底层开始遍历。上面的那道题如果理解了，这道题很简单，只是结果存储的方式变了一下而已。

题型五、二叉树中和为某一值的路径

思想：这道题其实就是一种深度搜索策略，同时可以发现是从根节点开始遍历，其实就是前序遍历，如果使用递归就得了解递归结束的条件。
具体思路：1）先从根节点开始深度遍历二叉树，前序遍历时，将该节点存储至path栈中（vector实现），使用path_value累加节点值；2）当遍历至叶节点时，检查path_value值是否为sum,若为sum，将path存入res中；3）在后序遍历时，将该节点值从path栈中弹出，path_value减去节点值。

leetcode 113

参考代码：

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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>>res;
        vector<int>path;
        int path_value=0;
        preorder(root,path_value,sum,path,res);
        return res;
    }
private:
   void preorder(TreeNode* root,int &path_value,int sum,vector<int>&path,vector<vector<int>>&res)
   {
       if(!root)return;
        path_value+=root->val;
        path.push_back(root->val);
        
        //如果是根节点，且路径和为sum时，将该路径加入res中去
       if(!root->left&&!root->right&&path_value==sum)
            res.push_back(path);
       preorder(root->left,path_value,sum,path,res);//如果不是根节点遍历左右节点
       preorder(root->right,path_value,sum,path,res);
       path_value-=root->val;//移除最后一个元素，深度遍历完一条路径后要回退
       path.pop_back();
   }
    
};

题型六、最近公共祖先

LeetCode 236

lower_common_ancestor.png
如上图所示，节点6的搜索路径是:3->5->6，节点4的搜索路径是：3->5->2->4。因此两个节点最近的公共祖先就是节点5。我们可以分别搜索这两个节点，然后将路径上的节点分别存储在两个vector中，然后比较两个vector就可以得到最近的公共祖先。
参考代码：

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
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*>path;
        vector<TreeNode*>res1;vector<TreeNode*>res2;
        int finish=0;
        preorder(root,p,path,res1,finish);
        finish=0;path.clear();
        preorder(root,q,path,res2,finish);
        int path_len=0;
        if(res1.size()>res2.size())path_len=res2.size();
        else path_len=res1.size();
        TreeNode*result=NULL;
        for(int i=0;i<path_len;i++)
        {
            if(res1[i]==res2[i])
                result=res1[i];
        }
        return result;
        
    }
private:
    void preorder(TreeNode* node,//正在遍历的节点
                  TreeNode* search,//待搜索的节点
                  vector<TreeNode*>&path,//遍历时的节点栈
                  vector<TreeNode*>&res,//最终搜索到的节点search的路径结果
                  int &finish//记录是否找到节点search变量，未找到时是0,找到为1
                 )
    {
        if(!node||finish)return;
        path.push_back(node);
        if(node==search)
        {
            finish=1;
            res=path;
        }
        preorder(node->left,search,path,res,finish);
        preorder(node->right,search,path,res,finish);
        path.pop_back();//结束遍历node时，将node节点弹出path栈
        
    }
};

题型七、二叉树的深度

LeetCode 104

参考代码：

1

题型八、二叉树的宽度

LeetCode 662

参考代码：

1
2