电商网站通用左侧弹出导航,设计模板网站,装饰公司怎么做微网站,企业查询网226. 翻转二叉树 简单 给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。 示例 1#xff1a; 输入#xff1a;root [4,2,7,1,3,6,9] 输出#xff1a;[4,7,2,9,6,3,1] 示例 2#xff1a; 输入#xff1a;root [2,1,3] 输出#x…226. 翻转二叉树简单给你一棵二叉树的根节点root翻转这棵二叉树并返回其根节点。示例 1输入root [4,2,7,1,3,6,9] 输出[4,7,2,9,6,3,1]示例 2输入root [2,1,3] 输出[2,3,1]示例 3输入root [] 输出[]提示树中节点数目范围在[0, 100]内-100 Node.val 100 核心笔记翻转二叉树 (Invert Binary Tree)1. 核心思想 (一句话总结)“照镜子对于树中的每一个节点都要交换它的左胳膊和右胳膊。”翻转二叉树并不是只翻转根节点的左右而是要递归地深入到每一个子节点把它们的左右孩子也都交换了。最终效果是整个树变成了镜像。2. 算法流程 (递归三步曲)终止条件 (Base Case)root null空节点没法翻转直接返回null。递归 (Recurse)left invertTree(root.left)先把左子树内部翻转好并拿回来。right invertTree(root.right)先把右子树内部翻转好并拿回来。操作 (Swap)关键动作root.left right,root.right left。将“处理好的右子树”挂到左边将“处理好的左子树”挂到右边。 代码回忆清单// 题目LC 226. Invert Binary Tree class Solution { public TreeNode invertTree(TreeNode root) { // 1. 终止条件 if (root null) { return null; } // 2. 递归处理子节点 (后序遍历视角) // 就像外包一样先让手下把左右两边的家务事处理好 TreeNode left invertTree(root.left); TreeNode right invertTree(root.right); // 3. 交换当前节点的左右指针 // 手下处理完了老板把自己左右手交换一下 root.left right; root.right left; return root; } }⚡ 快速复习 CheckList (易错点 扩展)[ ]先交换还是先递归都可以后序 (您的写法)先递归到底由下往上交换。前序先交换root.left和root.right然后再递归invertTree(root.left)和root.right。中序比较麻烦因为交换完左边后原来的右边变成了左边如果再递归右边其实是在递归“原来的左边”。需要小心处理。建议面试只写前序或后序。[ ]能不能用 BFS (层序遍历)面试加分项。可以把节点放入队列。每次取出一个节点交换它的左右孩子然后把左右孩子扔进队列。这样也能一层层完成翻转。[ ]必须返回值吗题目要求返回TreeNode所以递归函数最后要return root。️ 数字演练树结构4 / \ 2 7 / \ / \ 1 3 6 9递归到底: 此时root是 2。invert(1)- 返回 1。invert(3)- 返回 3。Swap: 2 的左变 3右变 1。返回(3-2-1)。递归到底: 此时root是 7。invert(6)- 返回 6。invert(9)- 返回 9。Swap: 7 的左变 9右变 6。返回(9-7-6)。回到根节点: 此时root是 4。left拿到了 (3-2-1)。right拿到了 (9-7-6)。Swap: 4 的左接 (9-7-6)右接 (3-2-1)。Result:4 / \ 7 2 / \ / \ 9 6 3 1