114.二叉树展开为链表
114.二叉树展开为链表
题解
思路：
1.将原来的左子树放到右子树 2.将原来的右子树，放到原来的左子树的最右边
1 / \ 2 5 / \ \ 3 4 6 //将 1 的左子树插入到右子树的地方 1 \ 2 5 / \ \ 3 4 6 //将原来的右子树接到左子树的最右边节点 1 \ 2 / \ 3 4 \ 5 \ 6 //将 2 的左子树插入到右子树的地方 1 \ 2 \ 3 4 \ 5 \ 6 //将原来的右子树接到左子树的最右边节点 1 \ 2 \ 3 \ 4 \ 5 \ 6 ......
代码
func flatten(root *TreeNode) { cur := root for cur != nil { if cur.Left != nil { //找左子树最右边的节点 lastNode := cur.Left for lastNode.Right != nil { lastNode = lastNode.Right } //将原来的右子树接到左子树的最右边节点 lastNode.Right = cur.Right //将左子树插入到右子树的地方 cur.Right = cur.Left cur.Left = nil } cur = cur.Right } }
func flatten(root *TreeNode) { if root == nil { return } flatten(root.Left) flatten(root.Right) oriRight := root.Right // 将左子树迁移到右子树 root.Left, root.Right = nil, root.Left // 找到新的右子树末端 lastNode := root for lastNode.Right != nil { lastNode = lastNode.Right } // 将原右子树拼接到新右子树末端 lastNode.Right = oriRight }
