leetcode:Binary Tree Upside Down

问题描述

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

 

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

 

   4
  / \
 5   2
    / \
   3   1  

 

原问题链接：https://leetcode.com/problems/binary-tree-upside-down/

 

问题分析

　　对于二叉树的问题，我们比较容易想到的是看能否有什么递归的方式来解决这个问题。这里我们可以利用这么一个思路：在某个节点的时候，我们把它的左子树颠倒，在颠倒完成后，原来那个左子树的左右子节点分别指向原来的根节点和原来的右兄弟节点。这样，在实现的时候，我们需要保存有一个当前子节点的上一级节点，在返回的时候设置。

　　详细的代码实现如下：

 

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) return null;
        TreeNode parent = root, left = root.left, right = root.right;
        if(left != null) {
            TreeNode ret = upsideDownBinaryTree(left);
            left.left = right;
            left.right = parent;
            return ret;
        }
        return root;
    }
}

 

非递归方式实现

　　基于上述递归实现的代码也可以转换成非递归的迭代实现方式，这种方式的实现如下：

 

public TreeNode upsideDownBinaryTree(TreeNode root) {
		TreeNode node = root, parent = null, right = null;
		while (node != null) {
			TreeNode left = node.left;
			node.left = right;
			right = node.right;
			node.right = parent;
			parent = node;
			node = left;
		}
		return parent;
	}

 

总结

　　对二叉树的上下颠倒转换比较复杂，需要结合递归和一些树的关系进行转换。最好结合树的结构图进行详细的转换推导。 

 

参考材料

http://bangbingsyb.blogspot.jp/2014/11/leetcode-binary-tree-upside-down.html

http://blog.csdn.net/whuwangyi/article/details/43186045