来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-upside-down

题目描述

给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。

你可以按下面的步骤翻转一棵二叉树：

原来的左子节点变成新的根节点
原来的根节点变成新的右子节点
原来的右子节点变成新的左子节点

上面的步骤逐层进行。题目数据保证每个右节点都有一个同级节点（即共享同一父节点的左节点）且不存在子节点。

示例 1：

输入：root = [1,2,3,4,5]
输出：[4,5,2,null,null,3,1]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 10] 内
1 <= Node.val <= 10
树中的每个右节点都有一个同级节点（即共享同一父节点的左节点）
树中的每个右节点都没有子节点

解题思路

经过观察发现仅仅是从下到上将父节点变成右结点，左结点变成父结点，右结点变成左结点，所以可以从下至上依次改变状态，可以使用栈来辅助寻找每一个结点，也可以使用前序遍历。

代码展示

栈辅助解法

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

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

 * };

 */

class Solution {

public:

    TreeNode* upsideDownBinaryTree(TreeNode* root) {

        TreeNode* p = root;

        stack<TreeNode*> szStack;

        if(root)

        {

            while(p)

            {

                szStack.push(p);

                p = p->left;

            }

            root = szStack.top();

            while(!szStack.empty())

            {

                p = szStack.top();

                szStack.pop();

                if(szStack.empty())

                {

                    p->left = nullptr;

                    p->right = nullptr;

                }

                else

                {

                    TreeNode* q = szStack.top();

                    p->left = q->right;

                    p->right = q;

                }

            }

        }

        return root;

    }

};

前序遍历解法

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

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

 * };

 */

class Solution {

public:

    TreeNode* mRoot;

    void dfs(TreeNode* root, TreeNode* fa)

    {

        if(!root) return;

        if(!root->left)

            mRoot = root;

        dfs(root->left, root);

        root->left = fa? fa->right : nullptr;

        root->right = fa;

    }

    TreeNode* upsideDownBinaryTree(TreeNode* root) {

        dfs(root,nullptr);

        return mRoot;

    }

};

巴特西

LeetCode-156 上下翻转二叉树

题目描述

解题思路

代码展示

运行结果

最新文章

热门文章