leetcode 114. Flatten Binary Tree to Linked List 扁平化二叉树+前序遍历

清疚 2022-06-08 04:16 93阅读 0赞

Given a binary tree, flatten it to a linked list in-place.

For example,  
Given

1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:  
1  
\\  
2  
\\  
3  
\\  
4  
\\  
5  
\\  
6  
click to show hints.

这道题很简答，就是做一次中序遍历，然后把它做回扁平化就可以了。

代码如下;

import java.util.ArrayList;
    import java.util.List;
    
    /*class TreeNode
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    public class Solution 
    {
        List<TreeNode> res=new ArrayList<TreeNode>();
        public void flatten(TreeNode root)
        {
            if(root==null)
                return ;
            preOrder(root);
            for(int i=0;i<res.size()-1;i++)
            {
                TreeNode one=res.get(i);
                TreeNode two=res.get(i+1);
                one.left=two.left=null;
                one.right=two;
            }
            TreeNode last=res.get(res.size()-1);
            last.left=last.right=null;
        }
    
        void preOrder(TreeNode root) 
        {
            if(root!=null)
            {
                res.add(root);
                preOrder(root.left);
                preOrder(root.right);
            }
    
        }
    }

下面是C++的做法，就是先做一个二叉树的前序遍历，然后按照要求去做就可以了

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        vector<TreeNode*> one;
        void flatten(TreeNode* root) 
        {
            getAll(root);
            if (one.size() >= 2)
            {
                for (int i = 1; i < one.size(); i++)
                {
                    one[i - 1]->right = one[i];
                    one[i - 1]->left = NULL;
                }
                one[one.size() - 1]->left = NULL;
                one[one.size() - 1]->right = NULL;
            }
            else
                return;
        }
    
        void getAll(TreeNode* root)
        {
            if (root == NULL)
                return;
            else
            {
                one.push_back(root);
                getAll(root->left);
                getAll(root->right);
            }
        }
    };