leetcode【中等】114、二叉树展开为链表

思路一&＃xff1a;递归先序遍历
中左右&＃xff0c;即把左放在右的位置&＃xff0c;再把右接在左的下面

class Solution:def flatten(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""if not root or (not root.left and not root.right):return #处理左右子树self.flatten(root.left)self.flatten(root.right)#中左右---中&＃xff0c;把左放在右&＃xff0c;把右放在左下面tmp&＃61;root.rightroot.right&＃61;root.leftroot.left&＃61;None#找到新树右的末尾&＃xff0c;把原右&＃xff08;tmp&＃xff09;接在后面while(root.right):root&＃61;root.rightroot.right&＃61;tmp


class Solution {public void flatten(TreeNode root) {if(root&＃61;&＃61;null || (root.left&＃61;&＃61;null && root.right&＃61;&＃61;null)){return;}flatten(root.left);flatten(root.right);TreeNode temp&＃61;root.right;root.right&＃61;root.left;root.left&＃61;null;while(root.right!&＃61;null){root&＃61;root.right;}root.right&＃61;temp;}
}


思路二&＃xff1a;非递归

class Solution:def flatten(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""stack&＃61;[]while root or stack:if root:stack.append(root)root&＃61;root.leftelse:node&＃61;stack.pop()tmp&＃61;node.rightroot&＃61;tmp#以上是前序遍历&＃xff0c;以下是每个结点处的操作node.right&＃61;node.leftnode.left&＃61;Nonewhile node.right:node&＃61;node.rightnode.right&＃61;tmp

class Solution {public void flatten(TreeNode root) {List<TreeNode>stack&＃61;new ArrayList<>();while(root!&＃61;null || stack.size()!&＃61;0){if(root!&＃61;null){stack.add(root);root&＃61;root.left;}else{TreeNode node&＃61;stack.remove(stack.size()-1);TreeNode temp&＃61;node.right;root&＃61;temp;node.right&＃61;node.left;node.left&＃61;null;while(node.right!&＃61;null){node&＃61;node.right;}node.right&＃61;temp;}}}
}