根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。
递归解析:
终止条件: 当节点 rootroot 为空时(即越过叶节点),则返回 nullnull ;
递推工作:
初始化节点 tmptmp ,用于暂存 rootroot 的左子节点;
开启递归 右子节点 mirrorTree(root.right)mirrorTree(root.right) ,并将返回值作为 rootroot 的 左子节点 。
开启递归 左子节点 mirrorTree(tmp)mirrorTree(tmp) ,并将返回值作为 rootroot 的 右子节点 。
返回值: 返回当前节点 rootroot ;
递归停止条件
递归事件:交换左右子节点,需要先暂存其中一个节点,root.left
递归一下右子节点将其赋给左子节点,
递归暂存节点即原左子节点将其赋给右子节点
返回root,返回值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root==null){
return null;
}//递归停止
TreeNode temp=root.left;
root.left=mirrorTree(root.right);
root.right=mirrorTree(temp);
return root;
}
}