树结构习题练习

1,判断二叉树是否对称

    1
     / \
    2   2
   / \ / \
  3  4 4  3

递归:

基本想法就是在函数中传入一边的左,和一边的右……

isSymmetric(leftNode.left, rightNode.right)

isSymmetric(leftNode.right, rightNode.left)

以这样的递归来不断比较。

public class SymmetricTree {
    static class TreeNode {
           int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(TreeNode leftNode, TreeNode rightNode){
        if(leftNode == null && rightNode == null ) return true;
        if(leftNode == null || rightNode == null) return false;
        if(leftNode.val != rightNode.val) return  false;
        boolean isLeft = isSymmetric(leftNode.left, rightNode.right);
        boolean isRight = isSymmetric(leftNode.right, rightNode.left);
        return isLeft && isRight;
    }

    public static void main(String args[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(new SymmetricTree().isSymmetric(root));
        System.out.println(new SymmetricTree().isSymmetricIter(root));
    }
}

  非递归的思路,就是分别遍历左右两边。只不过是反着次序遍历。

每次都各自出栈后往各自栈中放左右节点。一边是先放左后放右,一边是先放右后放左。

public boolean isSymmetricIter(TreeNode root) {
        if(root == null) return true;
        Stack<TreeNode> leftStack = new Stack<TreeNode>();
        Stack<TreeNode> rightStack = new Stack<TreeNode>();
        leftStack.push(root.left);
        rightStack.push(root.right);

        while (leftStack.size() > 0 && rightStack.size() > 0){
            TreeNode left = leftStack.pop();
            TreeNode right = rightStack.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val == right.val) {
                leftStack.push(left.right);
                leftStack.push(left.left);
                rightStack.push(right.left);
                rightStack.push(right.right);
            }else{
                return false;
            }
        }
        return true;
    }
时间: 07-13

树结构习题练习的相关文章

C#习题大全

C#习题大全 1.String str=new String("a")和String str = "a"有什么区别? String str = "a"; 这个只是一个引用,内存中如果有“a"的话,str就指向它,如果没有才创建如后还用到"a"这个字符串的话并且是这样用: String str1 = "a"; String str2 = "a"; String str2 = &q

查找-第9章-《数据结构题集》习题解析-严蔚敏吴伟民版

习题集解析部分 第9章 查找 ——<数据结构题集>-严蔚敏.吴伟民版        源码使用说明  链接??? <数据结构-C语言版>(严蔚敏,吴伟民版)课本源码+习题集解析使用说明        课本源码合辑  链接??? <数据结构>课本源码合辑        习题集全解析  链接??? <数据结构题集>习题解析合辑       相关测试数据下载  链接? 数据包       本习题文档的存放目录:数据结构\▼配套习题解析\▼09 查找       文档

数据库经典习题,

/* 数据导入: Navicat Premium Data Transfer Source Server : localhost Source Server Type : MySQL Source Server Version : 50624 Source Host : localhost Source Database : sqlexam Target Server Type : MySQL Target Server Version : 50624 File Encoding : utf-8

C/C++算法竞赛入门经典Page15 习题1-1 平均数

题目:输入3个整数,输出他们的平均值,保留3位小数. 首先,声明三个整数a,b,c和一个浮点数d: int a,b,c; double d; 输入三个整数a,b,c: scanf("%d%d%d",&a,&b,&c); 将a,b,c取平均值以后复制给d: d=(double)(a+b+c)/3; 最后输出d: printf("%.3lf",d); %.3lf表示保留3位小数的long float. 注意:不能直接这样输出: printf(&q

问题 1018: C语言程序设计教程(第三版)课后习题6.8

/******************************************************************** @file Main.cpp @date 2017-05-12 @author Zoro_Tiger @brief 问题 1018: C语言程序设计教程(第三版)课后习题6.8 http://www.dotcpp.com/oj/problem1018.html *************************************************

SICP 习题 (1.46)解题总结

SICP 习题 1.46 要求我们写一个过程iterative-improve,它以两个过程为参数,其中一个参数用来检测猜测是否足够好,另一个参数用来改进猜测.过程iterative-improve应该返回另一个过程,所返回的过程接收一个参数作为初始猜测,然后不断改进猜测直到结果足够好.题目还要求我们使用iterative-improve重写1.1.7的sqrt过程和1.3.3节的fixed-point过程. 因为涉及到高阶函数,所以整个题目理解起来有一点点费劲.不过这道题作为第一章的收官题确实

C++ Primer 学习笔记_74_面向对象编程 --再谈文本查询示例[续/习题]

面向对象编程 --再谈文本查询示例[续/习题] //P522 习题15.41 //1 in TextQuery.h #ifndef TEXTQUERY_H_INCLUDED #define TEXTQUERY_H_INCLUDED #include <iostream> #include <fstream> #include <sstream> #include <vector> #include <set> #include <map&g

pta 数据结构 习题2.4 递增的整数序列链表的插入(15 分)

习题2.4 递增的整数序列链表的插入(15 分) 本题要求实现一个函数,在递增的整数序列链表(带头结点)中插入一个新整数,并保持该序列的有序性. 函数接口定义: List Insert( List L, ElementType X ); 其中List结构定义如下: typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; type

linux习题回顾

linux习题回顾 1.1 创建一个压缩包/etc,我想让压缩包上面有个日期/时间. [[email protected] ~]# tar zcf /tmp/etc-$(date+%F).tar.gz /etc [[email protected] ~]# ls -l /tmp -rw-r--r--. 1 root root 9731838 Aug  3 19:15 etc-2017-08-03.tar.gz 1.2 已知/oldboy/test.txt文件内容为: oldboy xizi xi