C++ 小白入门leetcode (三）——tree 树 简单题目 详细解析_treenode c++

100. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

一：

class Solution {
public:
    static string s;
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL)return true;
        if(p==NULL||q==NULL)return false;
        return p->val==q->val&&isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
    }

};
1
2
3
4
5
6
7
8
9
10
11

二：非递归算法

class Solution {
public:
    static string s;
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> queuep, queueq;
        if(p==NULL&&q==NULL)return true;
        if(p==NULL||q==NULL)return false;
        queuep.push(p);
        queueq.push(q);
        while((!queueq.empty())&&(!queuep.empty())){
            TreeNode* tp, *tq;
            tp=queuep.front();
            queuep.pop();
            tq=queueq.front();
            queueq.pop();
            cout<<"tp"<<tp->val<<",tq"<<tq->val<<endl;
            if(tp->val!=tq->val)return false;
            if(tq->left!=NULL&&tp->left!=NULL){
                queuep.push(tp->left);
                queueq.push(tq->left);
            }
            else if(tq->left!=NULL||tp->left!=NULL)return false;
            if(tq->right!=NULL&&tp->right!=NULL)
            {
                queueq.push(tq->right);
                queuep.push(tp->right);
            }
            else if(tp->right!=NULL||tq->right!=NULL) return false;
        }   
    if( (!queueq.empty()) || (!queuep.empty()) ) return false;
    return true;
 }
};
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

101. 对称二叉树

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

解法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return f(root, root);
    }
    bool f(TreeNode* t1, TreeNode* t2){
        if(!t1&&!t2)return true;
        if(!t1||!t2)return false;
        if(t1->val==t2->val)return f(t1->left, t2->right)&&f(t1->right, t2->left);
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

判断的重点是一棵树的两个子树是不是相等的，为空、其中一个为空、不为空的话就判断这两个子树的根的节点，如果相同的话，就返回左树的左子树与右树的右子树。。。
递归基本上都是这个思路了。

解法二：层次遍历
思想相当于复制了一棵树，然后比较这两棵树。
每次比较队列的前两个节点，所以入队时前两个节点应当是对称的节点。

class Solution {
public:
bool isSymmetric(TreeNode* root)
{
    if (root == NULL)return true;
    queue<TreeNode*> q;
    q.push(root);
    q.push(root);
    
    while (!q.empty())
    {
        TreeNode* t1, * t2;
        t1 = q.front();
        q.pop();
        t2 = q.front();
        q.pop();
        if (t1 == NULL && t2 == NULL){continue;}
        if (t1 == NULL || t2 == NULL){return false;}
        if (t1->val != t2->val){return false;}
        q.push(t1->left);
        q.push(t2->right);   
        q.push(t1->right );
        q.push(t2->left );
    }
    return true;
}
};
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

使用队列是广度优先，使用栈是深度遍历。
这个题目也可以使用栈来解决；

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

解法一：
递归。思路是写一个函数，除了根节点增加一个参数dep来表示深度；
如果是空节点，就说明在本节点深度并不增加，返回dep的值即可；
否则，就返回他的左子树和右子树的深度，不过参数dep这时要+1.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth=0;
        return d(root, depth);

    }
    int d( TreeNode* ro, int  dep){
        if(ro==NULL)return dep;
        return max( d(ro->left, dep+1),d(ro->right , dep+1));

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

**解法二：**
1

也是递归，但是不用这一个参数，也不再另写一个函数。思路是为空就返回0，否则就是左右子树的深度+1.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root==NULL ? 0 : max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};
1
2
3
4
5
6

解法三：
最后当然要有非递归实现啦。
思路是使用一个队列，每次进一层的节点，然后出一层的节点（把他们的左右子节点入队）。
那么，就需要一个变量来记录每层的节点数目：layer_size。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth=0;
        queue<TreeNode*> que;
        if(root==NULL)return 0;
        que.push(root);
        while(!que.empty()){
            depth++;
            int layer_size=que.size();
            while(layer_size--){
                TreeNode* t=que.front();
                que.pop();
                if(t->left!=NULL)que.push(t->left);
                if(t->right!=NULL)que.push(t->right);
            }
        }
        return depth;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

107. 二叉树的层次遍历 II

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

解法一：
使用队列，就像普通的层次遍历一样。
但是题目要求的是从底向上输出，所以遍历每一层的时候把他加入vector的最前面而不是末尾；然后使用一个栈把每个一位vector从底向上加入二维vector（每一个一维的vector表示一行）。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> re;
        queue<TreeNode*> que;
        if(root==NULL)return re;
        que.push(root);
        int layer=0;
        stack<vector<int>> sta;
        while(!que.empty()){
            int layer_size=que.size();
            vector<int> a;
            while(layer_size--){
            TreeNode* t= que.front();
            que.pop();            
            a.push_back(t->val);
            if(t->left!=NULL)que.push(t->left);
            if(t->right!=NULL)que.push(t->right);            
            }            
            sta.push(a);
        }
        vector<int> temp;
        while(!sta.empty()){
            temp=sta.top();
            sta.pop();
            re.push_back(temp);
        }
        return re;
   
    }
};
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

方法二：
最后不用栈倒着插入每个一维vector了，而是直接在每一层的循环结束时，把它插入二维vector的头部，但是这样会慢一点，内存占用也大一点，这是vector：：insert（）函数的特点导致的。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> re;
        queue<TreeNode*> que;
        if(root==NULL)return re;
        que.push(root);
        int layer=0;
        while(!que.empty()){
            int layer_size=que.size();
            vector<int> a;
            while(layer_size--){
            TreeNode* t= que.front();
            que.pop();            
            a.push_back(t->val);
            if(t->left!=NULL)que.push(t->left);
            if(t->right!=NULL)que.push(t->right);            
            }            
            re.insert(re.begin(),a);
        }
        return re;   
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法三：
只有最后一个地方不同我就只贴最后的代码了。
用vector：：push——back压入末尾，但是最后reverse一下；就不需要使用栈来反转了；

            re.push_back(a);
        }
        reverse(re.begin(),re.end());
        return re;   
    }
};
1
2
3
4
5
6

方法四：逆向迭代器

       vector<vector<int>> result;
       for(auto iter=re.rbegin();iter!=re.rend();iter++) result.push_back(*iter);
        return result;   
    }
};
1
2
3
4
5

Auto真好用啊；

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点
的左右两个子树的高度差的绝对值不超过 1。

解法一：
利用数组的有序，每次都把位于数组中间的数，作为根节点，就像二分法查找一样。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(0,nums.size()-1, nums );
    }
    TreeNode* build(int left, int right, vector<int> num){
        if(left>right)return NULL;
        int mid=(left+right)/2;
        TreeNode* root=new TreeNode(num[mid]);
        root->left=build(left, mid-1, num);
        root->right=build(mid+1, right, num);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

110. 平衡二叉树

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

解法一：
递归。实际上是计算深度的函数，每次递归计算左右子树的深度，。。在计算深度的过程中，进行左右子树高度差的判断。设置一个布尔型的变量，来表示这棵树是不是平衡的；

class Solution {
public:
    bool balance = true;
    bool isBalanced(TreeNode* root) {
        f(root);
        return balance;
    }
    int f(TreeNode* root) {
        if (root == NULL) return 0;
        int left_d = f(root->left);
        int right_d = f(root->right);
        if (abs(left_d - right_d) > 1) balance = false;
        return max(left_d, right_d) + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解法二：
也是递归，但是就不用这一个变量来保存结果了。
用剪枝的思想，如果左右子树不平衡，那后面就不计算了，一路返回-1；（-1就表示不平衡）
与方法一相比，法一会计算出每一层的深度；

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return f(root) == -1 ? false : true;
    }
    int f(TreeNode* root) {
        if (root == NULL) return 0;
        int left_d = f(root->left);
        if (left_d == -1)return -1;
        int right_d = f(root->right);
        if (right_d == -1)return -1;
        if (abs(left_d - right_d) > 1) return -1;
        return max(left_d, right_d) + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

111. 二叉树的最小深度

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

读题要仔细，是到最近的叶子节点，如果是【1，2】这种树，那么输出是2不是1。
方法一：
使用队列，层次遍历。
找到一个左右子树为空的节点，就直接返回。否则的话继续层次遍历

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root==NULL)return 0;
        que.push(root);
        int layer=0;
        while(!que.empty()){
            int layer_size=que.size();
            if(layer_size)layer++;
            while(layer_size--){
                TreeNode* t=que.front();
                que.pop();
                if(t->left!=NULL)que.push(t->left);
                if(t->right!=NULL)que.push(t->right);
                if(t->left==NULL&&t->right==NULL) return layer;
            }    
        }
        return layer;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：
递归。
找到一个左右子树都为空的节点。
首先如果根节点是空的，就返回0；在后续的递归中不在把空节点作为参数传入；
如果左右子树都不为空，就要取他们的深度的最小值。

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

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
解法一：
递归。感觉这道题还挺难的；

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL)return false;
        if(root->left==NULL&&root->right==NULL) return sum-root->val==0;
        else return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val) ;
    }
};
1
2
3
4
5
6
7
8

解法二：
DFS，比较难想起来的点在于使用两个栈，保存当前节点的sum.
思路是把节点和它对应的sum同时压入两个栈中。
如果这是一个叶子节点（左右子树都为空）并且sum与他的当前值相等，就直接返回true；
否则就把他的左右节点压入栈中。

 class Solution {
  public:
      bool hasPathSum(TreeNode* root, int sum) {
          stack< TreeNode*> node;
          stack<int> newSum;
          if (root == NULL)return sum == 0;
          node.push(root);
          newSum.push(sum);
          while (!node.empty()) {
              TreeNode* t;
              int s;
              t = node.top();
              node.pop();
              s = newSum.top();
              newSum.pop();
              s -= t->val;
              if (t->left == NULL && t->right == NULL && s == 0) return true;
              if (s < 0)continue;
              if (t->left != NULL)
              {
                  node.push(t->left);
                  newSum.push(s);
              } 
              if (t->right != NULL) {
                    node.push(t->right);
                    newSum.push(s);
              }
          }
          return false;
      }
  };
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

226. 翻转二叉树

方法一：
递归，不使用swap函数。相当于新建一颗树，根节点就是root的根节点。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root){
        if(root==NULL)return NULL;
        TreeNode* mirror=new TreeNode(root->val);
        mirror->right=invertTree(root->left);
        mirror->left=invertTree(root->right);
        return mirror;
    }
};
1
2
3
4
5
6
7
8
9
10

解法二：
递归使用swap函数；
与刚才解法相比，没有创建一个新的树。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root){
            swap(root->left, root->right);
            root->left=invertTree(root->left);
            root->right=invertTree(root->right);
        }        
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11

235. 二叉搜索树的最近公共祖先

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

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

解法一：
思路是先把q搜索过程中经过的节点写进一个队列。
在搜索q的过程中，把路上经过的节点与队列比较，遇到的第一个不同的节点叫做a吧，那么最近的祖先节点就是a在队列中的上一个节点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que;
        int dp=depth(root, p);

        TreeNode * t=root;
        while(dp--){
            que.push(t);
            if(t->val<p->val)  t=t->right;
            else if(t->val>p->val)t=t->left;      
        }
        t=root;
        TreeNode* a=root;

        while(!que.empty()){
            
            if(a!=que.front()) return t;
            que.pop();
            t=a;
            if(t->val>q->val)a=t->left;
            if(t->val<q->val)a=t->right;
            
            
        }
        return t;
    }
    int depth(TreeNode* root, TreeNode* t){
         if(root==NULL)return 0;
         if(root->val==t->val) return 1;
         if(root->val>t->val)return depth(root->left,t)+1;
         else return depth(root->right, t)+1;
    }
};
 
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

解法二：
递归有点难想出来，重点是如果找到了一个根节点，p、q是位于他的两侧的。
所以如果p q都小于root，就说明他们都在root的左边。
大于反之；
一左一右，就说明这个root是他们最后一个祖先节点了。

  class Solution {
  public:
      TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
          int value_p = p->val, value_q = q->val, value_mid = root->val;
          if (value_p < value_mid && value_q < value_mid) return lowestCommonAncestor(root->left, p, q);
          if (value_p > value_mid && value_q > value_mid) return lowestCommonAncestor(root->right, p, q);
          else return root;

      }
  };
1
2
3
4
5
6
7
8
9
10