Leetcode刷题java之114. 二叉树展开为链表

分手后的思念是犯贱 2023-07-03 14:29 2阅读 0赞

执行结果：

通过

显示详情

执行用时 :0 ms, 在所有 Java 提交中击败了100.00% 的用户

内存消耗 :35.8 MB, 在所有 Java 提交中击败了86.84%的用户

题目：

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

1  
/ \\  
2 5  
/ \\ \\  
3 4 6

将其展开为：

1  
\\  
2  
\\  
3  
\\  
4  
\\  
5  
\\  
6

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

有点嫁接的意味，找到左子树的最右节点，然后让他的最右节点等于根的右节点，然后让根的右节点等于根的左节点。

参考[https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/][https_leetcode-cn.com_problems_flatten-binary-tree-to-linked-list_solution_xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26]

代码：

/**
     * 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)
                {
                    root=root.right;
                }else
                {
                    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;
                }
            }
        }
    }

[https_leetcode-cn.com_problems_flatten-binary-tree-to-linked-list_solution_xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26]: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/