[数据结构与算法]力扣算法 226.翻转二叉树 101.对称二叉树

学习内容

力扣算法

226.翻转二叉树

101.对称二叉树

具体内容

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

题目地址

做题思路

递归：

想象斐波那契数列的解法，具体可看博客
斐波那契数列递归解法

迭代：

由于是把每个子树的左右节点进行翻转，可以联想到层序遍历时用队列存储，再依次拿出来，翻转的话我们也可以按着这种思路，先存队列再拿出来。

解题

迭代

class Solution{
    //广度优先遍历 BFS 使用队列
    public TreeNode invertTree(TreeNode root) {
    	//创建队列
    	Queue<TreeNode> queue = new Queue<>();
    	//将根节点放进队列中
    	if(root != null){
    		queue.offer(root);
    	}
    	while(!queue.isEmpty()){
    		TreeNode node = queue.pop();
    		swap(node);
    		if(node.left != null){queue.offer(node.left);}
    		if(node.right != null){queue.offer(node.right);}
    	}
    	return root;
    }
    //进行翻转
    public void swap(TreeNode node){
    	TreeNode temp = node.left;
    	node.left = node.right;
    	node.right = temp;
    }

递归

class Solution{
    //广度优先遍历 BFS 使用队列
    public TreeNode invertTree(TreeNode root) {
		if (root == null) {
            return null;
        }
        swap(root);
        if(root.left!=null){invertTree(root.left);}
        if(root.right!=null){invertTree(root.right);}
        return root;
    }
    //进行翻转
    public void swap(TreeNode node){
    	TreeNode temp = node.left;
    	node.left = node.right;
    	node.right = temp;
    }
}

101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

题目地址

做题思路

递归

想象斐波那契数列的解法，具体可看博客
斐波那契数列递归解法

迭代

依然联想到使用队列，将节点放入队列之中再进行比较。而本题时判断是否对称，可以先从三种不对称情况入手：1、左节点的左节点为空，右节点的右节点不为空 2、左节点的右节点为空，右节点的左节点不为空 3、两个节点值不相等

解题

迭代

class Solution {
    //迭代法 ，使用双队列,与他的排列顺序有关
    //先写出不满足条件的
    public boolean isSymmetric(TreeNode root) {
    	//双队列
    	Queue<TreeNode> queue = new ArrayQueue<>();
    	//双队列 左右节点分别从两侧进入
    	queue.offerFirst(root.left);
    	queue.offerLast(root.right);
    	while(!queue.isEmpty()){
    	//存在左右节点为空，因为遍历到最下
    		TreeNode node1 = queue.pollFirst();
    		TreeNode node2 = queue.pollLast();
    		if(node1 == null && node2 == null){
    			//这里虽然是到了叶子节点 但就不代表已经到了底层
    			//return true;
    			continue;
    		}
    		if(node1 == null || node2 == null || node1.val!= node2.val){
    			return false;
    		}
    		queue.offerFirst(node1.left);
    		queue.offerFirst(node1.right);
    		queue.offerLast(node2.right);
    		queue.offerLast(node2.left);
    	}
    	return queue;
    }
   } 
 }

递归

class Solution {
//迭代法 ，使用双队列,与他的排列顺序有关
    //先写出不满足条件的
    public boolean isSymmetric(TreeNode root) {
       return compare(root.left,root.right);
    }
    //题目是对子树的左右节点比较 就要先确定递归的参数 我们要比较的时左右子树 那么就传左 右节点
    public boolean compare(TreeNode left,TreeNode right){
        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean left1 = compare(left.left,right.right);
        boolean right1 = compare(left.right,right.left);
        return left1 && right1;
    }
 }