114. 二叉树展开为链表

解题思路

• 后序遍历思路
• 将root的左子树和右子树展平
• 将root的右子树接到左子树下方 然后将整个左子树作为右子树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {// 将root的左子树和右子树展平// 将root的右子树接到左子树下方  然后将整个左子树作为右子树if(root == null){return ;}// 后序遍历的思路// 首先递归将树展平flatten(root.left);flatten(root.right);// 后序遍历 // 临时保存左子树TreeNode left = root.left;// 临时保存右子树TreeNode right = root.right;root.left = null;// 将root的左子树作为右子树root.right = left;// 将原先的右子树接到当前右子树的末端TreeNode temp = root;// 找到当前右子树的末尾while(temp.right != null){temp = temp.right;}temp.right = right;// 将原先的右子树连接到现在的右子树的末尾}
}