【递归】【后续遍历】【迭代】【队列】Leetcode 101 对称二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了【递归】【后续遍历】【迭代】【队列】Leetcode 101 对称二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

---------------🎈🎈对称二叉树题目链接🎈🎈-------------------

【递归】【后续遍历】【迭代】【队列】Leetcode 101 对称二叉树,Leetcode,leetcode,算法,职场和发展,数据结构,java

解法一：递归：后序遍历左右中

时间复杂度O(N)
空间复杂度O(N)文章来源地址https://www.toymoban.com/news/detail-825885.html

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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 true;}
        if(left != null && right==null){return false;}
        if(left == null && right!=null){return false;}
        if(left.val != right.val){return false;}

    // 递归逻辑：继续比较左右两个子树的内外侧【相当于后序遍历，最后返回内侧和外侧的比较结果】
        boolean compareOutside = compare(left.left, right.right); 
        boolean compareInside = compare(left.right, right.left);
        return compareInside && compareOutside;  // 内外侧都是true的时候就返回true

    }

}

解法二：迭代法，用了单端队列

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 采用迭代法:用了单端队列
        Queue<TreeNode> myqueue = new LinkedList<>();
        myqueue.add(root.left);
        myqueue.add(root.right);
        while(!myqueue.isEmpty()){
            TreeNode leftnode = myqueue.poll();
            TreeNode rightnode = myqueue.poll();
            if(leftnode == null && rightnode == null){
                continue;
            }

            if(leftnode != null && rightnode == null){
                return false;
            }
            if(leftnode == null && rightnode != null){
                return false;
            }
            if(leftnode.val != rightnode.val){
                return false;
            }

            myqueue.add(leftnode.left);
            myqueue.add(rightnode.right);
            myqueue.add(leftnode.right);
            myqueue.add(rightnode.left);
        }
        return true;

    }
}