LeetCode 114. 二叉树展开为链表

蔚落 2022-11-05 08:51 132阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]  
[大佬][Link 1]

//左右中 先把俩子树拉直，然后把左子树换成右子树，这时原来的左子树变成新的右子树，找到新右子树的最后一个节点连接旧的右子树
    /**
     * 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 {
        
        TreeNode pre = null;
        public void flatten(TreeNode root) {
        
            if(root == null)
                return;
            flatten(root.left);
            flatten(root.right);
            TreeNode tmp  = root.right;
            root.right = root.left;
            TreeNode foot = root;
            while(foot.right != null) foot = foot.right;
            foot.right = tmp;
            root.left = null;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221023/c480cf7eaae7432ab85aadd667c509c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221023/d2786e1c835f4b9b94552361ebb3d1f9.png
[Link 1]: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/jian-dan-di-gui-by-bu-zhi-yin-sdrt/