一。题目
分析:
(1)要求转化为先序遍历顺序,这个很容易想到设置一个链表,然后先序遍历二叉树,把节点和指针记录在链表就好了
(2)题目要求in-place,也就是说不允许申请额外空间了,所以不能设置一个新的链表,只能在当前树(左右孩子指针)的结构上做手脚了,而且从图上看最后的二叉树都是只有右子树的。
由上图可知,如果右子树不为空,则右子树最后肯定为左子树最后一个靠右的孩子节点的右子树,而左子树最后成为整棵树的右子树。这样,首先判断左子树是否为空,不为空就寻找到树根的左孩子节点,然后寻找该节点是否有右孩子,如果有继续寻找,直到找到属于叶子节点的右孩子,此时,该节点的右子树“指向”当前树的右子树,并将当前左子树变为树根的右孩子,将整棵树左孩子置为空。最后,根节点“指向”根节点的右孩子,继续上述操作,直到整棵树遍历完即得到结果。
举个例子,比如只有2,3,4这三个节点,原先2左指针指向3,右指针指向4,现在不行了,需要把3指向4,断开2和4的连接,也就是要2的左孩子指向2的右孩子。然后形成一个递归的感觉。
java1:非递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
while(root!=null){
if(root.left!=null){
TreeNode pre=root.left;
while(pre.right!=null){
pre=pre.right;
}
pre.right=root.right;
root.right=root.left;
root.left=null;
}
root=root.right;
}
}
}
java2:递归
public void flatten(TreeNode root) {
if (root == null) return;
if (root.left != null) {
TreeNode cur = root.left;
while (cur.right != null) {
cur = cur.right;
}
cur.right = root.right;
root.right = root.left;
root.left = null;
}
flatten(root.right);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)