leetcodeブラシノート-ツリー2

leetcode 101:

/*

       ，           。

  ，    [1,2,2,3,4,4,3]     。

    1
   / \
  2   2
 / \ / \
3  4 4  3


       [1,2,2,null,3,null,3]         :

    1
   / \
  2   2
   \   \
   3    3

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/symmetric-tree
          。           ，          。
*/
/*
  ，                      ，               
*/
#include
#include

 struct TreeNode {
     
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {
     }
 };
 
class Solution {
     
public:
    bool isSymmetric(TreeNode* root) {
     
        if (root == NULL)
        {
     
            return true;
        }
        else
        {
     
            return DFS(root->left,root->right);
        }
        

    }
    bool DFS(TreeNode *rootleft,TreeNode *rootright)
    {
     
        //    NULL       
        if (rootleft == NULL && rootright == NULL)
        {
     
            return true;
        }
        //     NULL            
        if ((rootleft == NULL && rootright != NULL) || (rootleft != NULL && rootright == NULL))
        {
     
            return false;
        }
        //                           ，               
        auto res = rootleft->val == rootright->val && DFS(rootleft->left, rootright->right) && DFS(rootleft->right,rootright->left);
        return res;
    }
};

leetcode 104:

/*
       ，       。

                           。
*/
#include 
#include 
using namespace std;

struct TreeNode
{
     
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) :val(x), left(NULL), right(NULL) {
     }
};
class Solution
{
     
public:
	int maxDepth(TreeNode* TreeNode)
	{
     
		if (TreeNode == NULL)        
		{
     
			return 0;
		}
		else
		{
     
			int left_depth = maxDepth(TreeNode->left);
			int right_depth = maxDepth(TreeNode->right);
			return max(left_depth, right_depth) + 1;  //      1       0 
		}

	}
};

leetcode 105:

/*
                    。

  :
              。

  ，  

     preorder = [3,9,20,15,7]
     inorder = [9,3,15,20,7]
        ：

    3
   / \
  9  20
    /  \
   15   7

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
          。           ，          。
*/

/*

    ： - - 
    ： - - 
              ，          ，               ，             

*/
#include
#include
using std::vector;



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

class Solution {
     
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
     
        std::cout << "  " << std::endl;
        if (preorder.size() == 0 || inorder.size() == 0)
        {
     
            return NULL;
        }
        else
        {
     
            return  build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
        }

    
    }
public:
    TreeNode* build(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie)
    {
     
        //      
        TreeNode* root = new TreeNode(preorder[ps]);
        root->left = NULL;
        root->right = NULL;
        //            
        int rootval = preorder[ps];
        //             ，      ，            
        //            
        int mid = 0;
        for (int i = is; i <= ie; i++)
        {
     
            if (rootval == inorder[i])
            {
     
                mid = i;
                break;
            }
        }
        //      
        int leftlen = mid - is;
        int rightlen = ie - mid;
        
        //       
        if (leftlen > 0)
        {
     
            //           ，            
            root->left = build(preorder, ps+1,ps+leftlen , inorder, is, is+leftlen-1);
        }
        if (rightlen > 0)
        {
     
            root->right = build(preorder,ps+leftlen+1,pe,inorder,is+leftlen+1,ie);
        }
        return root;
    }
};

leetcode 106:この問題は前の問題と同じ方法です.

/*
                    。                    。

  :
              。

  ，  

     inorder = [9,3,15,20,7]
     postorder = [9,15,7,20,3]
        ：

    3
   / \
  9  20
    /  \
   15   7

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
          。           ，          。*/
/*
    ：      
    ： - - 
                ，                   
*/

#include
#include
using std::vector;

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

class Solution {
     
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
     
        if (inorder.size() == 0 || postorder.size() == 0)
        {
     
            return NULL;
        }
        else
        {
     
            return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
        }

    }
public:
    TreeNode* build(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe)
    {
     
        //     
        TreeNode* root = new  TreeNode(postorder[pe]);
        root->left = NULL;
        root->right = NULL;

        int rootval = postorder[pe];
        //             ，      ，            
        //            
        int mid = 0;
        for (int i = is; i <= ie; i++)
        {
     
            if (rootval == inorder[i])
            {
     
                mid = i;
                break;
            }
        }

        int leftlen = mid - is;
        int rightlen = ie - mid;

        if (leftlen > 0)
        {
     
            root->left = build(inorder, is, is + leftlen - 1, postorder, ps, pe - 1 - rightlen);
        }
        if (rightlen > 0)
        {
     
            root->right = build(inorder, is + leftlen + 1, ie, postorder, pe - rightlen, pe - 1);
        }

        return root;
    }
};