leetcode解题: Binary Tree Upside Down (156)

发表于 | 分类于

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

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

return the root of the binary tree [4,5,2,#,#,3,1].

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

解法1：

用分治的方法思考比较容易， 题目的意思是只有两种情况，一种是没有右子树，但可能有左子树，一种是有右子树但一定也有左子树。
变换之后，right tree变成left， root变成left， 而原来的left也需要进行upside down的变化。最后他的root是最终的root， 而他的最右子树变成了现在root和right的parent
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
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct res {
    TreeNode* root;
    TreeNode* tail;
    res(TreeNode* r, TreeNode* t):root(r),tail(t) {}
};
class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        res result = helper(root);
        return result.root;
    }
    res helper(TreeNode* root) {
        if (!root) {
            return res(NULL, NULL);
        }
        if (!root->left && !root->right) {
            return res(root, root);
        }
        res left = helper(root->left);
        left.tail->left = root->right;
        left.tail->right = root;
        root->left = NULL;
        root->right = NULL;
        return res(left.root, root);
    }
};

Java

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
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class NodeMark {
        TreeNode root;
        TreeNode tail;
        public NodeMark(TreeNode root, TreeNode tail) {
            this.root = root;
            this.tail = tail;
        }
    };
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) return root;
        NodeMark temp = helper(root);
        return temp.root;
    }
    private NodeMark helper(TreeNode root) {
        if (root == null) {
            return new NodeMark(null, null);
        }
        if (root.left == null && root.right == null) {
            return new NodeMark(root, root);
        }
        NodeMark left = helper(root.left);
        left.tail.left = root.right;
        left.tail.right = root;
        root.left = null;
        root.right = null;
        return new NodeMark(left.root, root);
    }
}