对称二叉树之经典递归思想 + 递归借助栈转迭代

• 前言
• 一、对称二叉树
• 二、递归与迭代
• • 1、递归回溯
  • 2、栈与迭代
• 总结
• 参考文献

二叉树的结构为root，左子树，右子树，左右子树也同时具备root，左子树和右子树，所以二叉树是一个典型的递归结构。保持递归遍历对二叉树的敏感性，打好递归和非递归遍历基础，是操作二叉树的第一步。
前中序遍历–经典递归；
后续遍历–回溯操作。

//对称二叉树
public class IsSymmetric {
    
    public boolean isSymmetric(TreeNode root) {
        if (null == root) return true;

        return order(root.left, root.right);
    }

    
    private boolean order(TreeNode rl, TreeNode rr) {
        //空子树 等于 空子树  =>  对称！
        if (rl == null && rr == null) return true;
        //有至少一个不等于null
        if (rl == null || rr == null || rl.val != rr.val) return false;//前序遍历比较

        //rl的左子树和rr的右子树相等，且rl的右子树与rr的左子树相等，则判为对称，返回true。
        return order(rl.left, rr.right) && order(rl.right, rr.left);
    }


    // 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 IsSymmetric2 {
    
    public boolean isSymmetric(TreeNode root) {
        if (null == root) return true;

        return iterator(root.left, root.right);
    }

    
    private boolean iterator(TreeNode rl, TreeNode rr) {
        Stack sk1 = new Stack<>();
        Stack sk2 = new Stack<>();

        if (rl != null) sk1.add(rl);
        if (rr != null) sk2.add(rr);

        while (!sk1.isEmpty() && !sk2.isEmpty()) {
            TreeNode n1 = sk1.pop();
            TreeNode n2 = sk2.pop();

            if (n1.val != n2.val) return false;
            //按 左右与右左的顺序将节点装入栈中。
            if (n1.left != null && n2.right != null) {
                sk1.add(n1.left);
                sk2.add(n2.right);
            } else if (n1.left != null || n2.right != null) return false;
            if (n1.right != null && n2.left != null) {
                sk1.add(n1.right);
                sk2.add(n2.left);
            } else if (n1.right != null || n2.left != null) return false;
        }
        return sk1.isEmpty() && sk2.isEmpty();
    }


    // 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;
        }
    }

}

1）递归回溯是树与二叉树的基础。
2）对于递归，逻辑性显得尤为重要，用心理清逻辑，递归代码比较简洁，那么逻辑性要求就更高一点。
3）栈模拟递归的练习。

[1] LeetCode 对称二叉树